• 离散数学

    Kenneth H. Rosen编写的Discrete Mathematics and Its Applications 8th

     

    基础:逻辑和证明

    命题逻辑

    原子命题:不能用更简单的命题来表达的命题。

    逻辑符号

    符号英文中文
    ¬p (not p)negation反面,对立面(非)
    pq (p and q)conjunction合取(与)
    pq (p or q)disjunction析取(或)
    pq (p xor q)exclusive or异或(一真一假命题为真)

    条件语句

    pq表示如果p,那么q,其中p被称为假设(或先行词或前提),q称为结论(或结果)只有当p为真,q为假,pq才为假,否则为真。

    pqpq
    TTT
    TFF
    FTT
    FFT

    逆命题(converse)qp

    逆否命题(contrapositive)¬q¬p,命题成立与逆否命题成立等价

    双条件命题(biconditional statement)pq,p、q均成立为真,否则为假。

    一些标记ponlyifq表示只有q时,才有p;如果q不成立,那么p一定不成立,即qp的必要条件。那么可以得到pq的充分条件,用ifp,thenq表示。

    pqp only if qpqq only if p
    TTTTT
    TFFFT
    FTTTF
    FFTTT

    qunless¬pifp,thenq的意思相同,这句话的意思是如果¬p为假,那么q一定为真,也就是说,当p为真但q为假时,命题" q除非¬p "为假,否则命题为真。因此," q除非¬p"和p→q总是具有相同的真值

    已知 pq,则

    逆命题(converse)qp

    逆否命题(contrapositive)¬q¬p,只有当¬p为假,而¬q为真时该命题为假,否则为真

    否命题(inverse)¬p¬q,只有当¬q为假,而¬p为真时该命题为假,否则为真

    双条件命题(biconditional)pq,只有当p和q的取值相同才为真,相当于(p → q) ∧ (q → p)。

    复合命题的真值表

    考虑一个复合命题:(p¬q)(pq),则仅p¬q为真时,pq为假时,该复合命题为假

    pqp¬qpq(p¬q)(pq)
    TTTTT
    TFTFF
    FTFFT
    FFTFF

    逻辑操作符的顺序

    OperatorPrecedence
    ¬1
    2
    3
    4
    5

     

    命题逻辑的应用

    语句翻译成逻辑

    语句:“You can access the Internet from campus only if you are a computer science major or you are not a freshman.”

    逻辑:p(q¬f),p代表You can access the Internet from campus,q代表you are a computer science major,f代表you are a freshman

    语句:“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.”

    逻辑:(p¬q)¬f,p代表you are under 4 feet tall,q代表You are older than 16 years old,f表示You can ride the roller coaster

    Bool搜索

    在布尔搜索中,连接的AND用于匹配同时包含两个搜索词的记录,连接的OR用于匹配两个搜索词中的一个或两个,连接的NOT(有时写成AND NOT)用于排除特定的搜索词。当使用布尔搜索来定位可能感兴趣的信息时,通常需要仔细规划如何使用逻辑连接词。

     

    命题等价

    无论其中出现的命题变量的真值是多少,一个复合命题总是为真,这就叫做重言式(永真式,tautology)。一个总是假的复合命题叫做矛盾式(contradiction)。既不是永真式也不是矛盾式的复合命题称为可能式(contingency)。

    逻辑等价

    如果pq是重言式,则两个复合命题pq逻辑等价,用pq表示,注意并不是一个逻辑连接符,而是表示pq是一个重言式。

    De Morgan法则¬(pq)=¬p¬q,¬(pq)=¬p¬q

    条件析取等价pq¬pq,左边当p为真,q为假时,命题为假;右边当p为真,q为假时,命题为假

    分配律p(qr)(pq)(pr),p(qr)(pq)(pr)

    结合律(pq)rp(qr),(pq)rp(qr)

    吸收律p(pq)=p,p(pq)=p

    image-20231020221725176

    构造新的逻辑等价

    证明¬(pq)p¬q逻辑等价

    ¬(pq)=¬(¬pq)=p¬q

    可满足性

    对于一个复合命题,如果给它的变量赋真值,使它为真(也就是说,当它是重言式或偶然性时),则称这个复合命题是可满足的。

    应用:n-皇后问题

    n皇后问题要求在一个n × n的棋盘上放置n个皇后,这样任何皇后都不能攻击另一个皇后。这意味着不能将两个皇后放在同一行、同列或同一对角线上。图1显示了8皇后问题的解决方案。(八皇后问题可以追溯到1848年,当时由马克斯·贝泽尔提出,并于1850年由弗朗茨·纳克彻底解决。

    为了将建模n-皇后问题成一个满足性问题,我们引入n2变量p(i,j),i=1,2,...,n,j=1,2,...,n,对于一个皇后在棋盘上的给定位置,p(i,j)在正方形第i行第j列有皇后时为真,反之为假。请注意,如果i+i=j+jii=jj,则正方形(i, j)和(i',j')位于同一对角线上。

    如果要求n个皇后没有两个在同一行,所以每行只有一个皇后,我们可以通过验证每行至少包含一个皇后,每行最多包含一个皇后来证明每行中有一个皇后。可以使用

    Q1=i=1nj=1np(i,j)

    对于每一行,让j=1np(i,j)为真表示至少有一个皇后,i=1nj=1np(i,j)为真则表示每行都至少有一个皇后,同样也保证了每列至少有一个皇后。

    对于每行最多只有一个皇后,对于整数j和k,且1j<kn,需要保证p(i,j)p(i,k)不同时为真,可以通过¬p(i,j)¬p(i,k)表示,对于每一行:

    Q2=i=1nj=1n1k=j+1n(¬p(i,j)¬p(i,k))

    同样对于每一列,有

    Q3=j=1ni=1n1k=i+1n(¬p(i,j)¬p(k,j))

    要求对角线没有多个皇后,先看向左上的对角线

    Q4=i=2nj=1n1k=1min(i1,nj)(¬p(i,j)¬p(ik,k+j))

    再看右下的对角线

    Q5=i=1n1j=1n1k=1min(ni,nj)(¬p(i,j)¬p(i+k,k+j))

    最后需要满足可满足性为

    Q=Q1Q2Q3Q4Q5

    还有数独的例子不过多赘述。

    谓词和量词

    谓词

    如让P(x)表示表述“x>3”,P(4)为真,P(3)为假。

    前置条件和后置条件:谓词还可以用来验证计算机程序,也就是证明当给定合法输入时计算机程序总是能产生所期望的输出。(注意除非建立了程序的正确性,否则无论测试了多少次都不能证明程序对所有输入都产生所期望的输出,除非能测试到每个输入值。)描述合法输入的语句叫作前置条件,而程序运行的输出应该满足的条件称为后置条件。

    考虑下面的程序

    前置语句P(x,y):假设“x=a,y=b”成立,后置语句Q(x,y):“x=b, y=a”。

    量词

    全称量词:许多数学命题断言某一性质对于变量在某一特定域内的所有值均为真,这一特定域称为变量的论域(domain of discourse)(或全体域( universe of discourse)), 时常简称为域(domai n) 。这类语句可以用全称量化表示。

    存在量词:许多数学定理断言:有一个个体使得某种性质成立。这类语句可以用存在量化表示。我们可以用存在批化构成这样一个命题:该命题为真当且仅当论域中至少有一个x的值使得P(x)为真。

    命题什么时候为真什么时候为假
    xP(x)对每一个x,P(x)为真有一个 x, 使 P(x)为假
    xP(x)有一个x,使P(x)为真对每一个x,P(x)都为假

    有限域上的量词

    当一个量词的域是有限的,则可以用命题逻辑来表示,当论域中的元素为x1,x2,...,xn,则:

    xP(x)P(x1)P(x2)...P(xn)xP(x)P(x1)P(x2)...P(xn)

    量词的优先级

    量词比命题演算中的所有逻辑运算符都具有更高的优先级。比如,xP(x)Q(x)xP(x)Q(x)的析取。换句话说,它表示(xP(x))Q(x),而不是x(P(x)Q(x))

    量化表达式的否定

    ¬xP(x)x¬P(x)

    ¬xP(x)为真当且仅当xP(x)为假,则P(x)至少存在一个假,则¬P(x)至少存在一个真,则x¬P(x)为真,同理可以得到¬xP(x)为假时,x¬P(x)也为假,所以两者等价。

    x(x2>x)的否定为x¬(x2>x)x(x2x)x(x2=2)的否定为x¬(x2=2)x(x22)

    系统规范说明中量词的使用

    用谓词和量词表达系统规范说明“每封大于1MB的邮件会被压缩”和“如果一个用户处于活动状态,那么至少有一条网络链路是有效的”。

    “每封大于1MB的邮件会被压缩”:令S(m,y)表示邮件m大于yMB,其中变量的m的论域是所有邮件,变量y是一个正实数;令C(m)表示“邮件m会被压缩”。可以表述为:m(S(m,1)C(m))

    “如果一个用户处于活动状态,那么至少有一条网络链路是有效的”:令A(u)表示“用户u处于活动状态”,其中变量u的论域是所有用户;令S(n,x)表示网络链路n处于x状态,其中n的论域是所有网络链路,x的论域是网络链路所有可能的状态。可以表述为:uA(u)nS(n,work)

    嵌套量词

    一个量词出现在另一个量词的作用域,如xy(x+y=0)可以表示为xQ(x),而Q(x)y(x+y=0)

    理解涉及嵌套量词的语句

    xy(x+y=0)表示为对于所有x,存在y,使x+y=0,即每个实数都有一个加法的逆

    xy((x>0)(y<0)(xy<0)),表示对于所有x和y,当x>0且y<0时,都有xy<0。

    将“每个人恰好有一个最好的朋友”翻译成逻辑表达式

    对于一个人x恰好有一个最好的朋友,可以表示为存在一个人y是x最好的朋友,同时其他不是y的人z都不是x最好的朋友,x最好的朋友是y用B(x,y)表示。

    xy(B(x,y)z((zy)¬B(x,z)))

    嵌套量词的否定

    直接连续地应用单个量词语句的否定规则即可

    xy(xy=1)的否定为xy(xy1)

     

    推理规则

    语句((pq)p)q是一个永真式,是假言推理(modus ponens)或分离规则(law of detachment)的推理规则的基础。

    ppqq

    image-20231021102845158

    谬误

    命题((pq)q)p不是永真式,因为当p为假,q为真时,左边为真,而右边为假,这种称为肯定结论的谬误(allacy of affirming the conclusion)

    命题((pq)¬p)¬q不是永真式,当p为假q为真时,左边为真,而右边为假,这种称为否定假设的谬误(allacy of denying the hypothesis)。

    量化命题的推理规则

    全称实例(universal instantiation)是从给定前提xP(x)得出P(c)为真的推理规则;

    全称引入(universal generalization)是从对论域里所有元素c都有P(c)为真的前提推出xP(x)为真的推理规则;

    存在实例(existential instantiation)是允许从“如果我们知道xP(x)为真,得出在论域中存在一个元素c使得P(c)为真”的推理规则;

    存在引入(existential generalization)是用来从“已知有一特定的c使P(c)为真时得出xP(x)为真”的推理规则。

    命题和量化命题推理规则的组合使用

    全称假言推理(universal modus ponens):如果x(P(x)Q(x))为真,并且如果P(a)对在全称量词论域中的一个特定元素a为真,那么Q(a)肯定为真。

    x(P(x)Q(x))P(a),adomainxQ(a)

    证明导论

    证明方法

    1. 直接证明法:pq

    2. 反证法:¬q¬p

    3. 归谬证明法:

    假设我们要证明命题p是真的。再假定我们能找到一个矛盾式q使得¬pq为真。因为q是假的,而¬pq是真的,所以我们能够得出结论¬p为假,这意味着p为真。

    如证明任意22天中至少有4天属于每星期的同一天

    令p为命题“任意 22 天中至少有 4 天属于每星期的同一天”。假设¬p为真。这意味着 22 天中至多有 3 天属于每星期的同一天。因为一个星期有 7 天,这蕴含至多可以选择 21天,对于每星期的同一天,最多可以选三天属于这一天。这个与我们题中有 22 天的前提相矛盾。也就是说,如果 r 是命题 “22 天”,则我们已经证明了¬p(r¬r)。所以,我们知道p是真的。我们证明了 22 天中至少有 4 天属于每星期的同一天。

    证明的方法和策略

    给出了许多证明方法和策略

    1. 穷举证明法和分情形证明法

    2. 存在性证明,构造性和非构造性

    3. 唯一性证明,要证存在性和唯一性

    4. 证明策略:正向推理和反向推理

    5. 寻找反例

    6. 证明策略实践:棋盘拼接问题

    证明或驳斥:如果你有一个盛有8加仑水的瓶和两个容量分别为5加仑和3加仑的空瓶,那么你可以通过不断地把一瓶水全部或部分倒人另一个瓶中而测量出4加仑的水。

    证明:令盛有8加仑水的瓶为A,容量为5加仑水的瓶为B,容量为3加仑的瓶为C

    可以找到这样一种方法满足测量出4加仑水的方法。

     

    基本结构:集合、函数、序列、求和与矩阵

    集合

    花名册表示法:{a,b,c,d}

    相等集合:两个集合包含相同的元素称为相等集合,如{1,3,3,5,5,5,5}和{1,3,5}是同一个集合

    空集:不含任何元素的集合,空集的唯一元素是空集本身

    单元素集:只有一个元素的集合

    基数:令S为集合,S的基数记为|S|

    幂集:给定集合S,S的幂集是集合S所有子集的集合,S的幂集记为P(S)

    多重集:是一个元素的无序集,其中元素作为成员可以出现多于一次,如{m1,a1,m2,a2,...}

    函数

    一对一(one-to-one)或单射(injection)函数:当且仅当对于f的定义域中的所有a和b有f(a)=f(b)蕴含a=b。ab(f(a)=f(b)a=b)或者ab(abf(a)f(b))

    映上(onto)或满射(subjection)函数:当且仅当对每个bB有元素aA使得f(a)=b,yx(f(x)=y)

    一一对应(one-to-one correspondence)或双射(bijection)函数:既是一对一又是映上的。

    下取整函数(floor):x,上取整函数(ceiling):x,注意x=x,x=x

    集合的基数

    康托尔-伯恩施坦定理:如果A和B是集合且|A||B||A||B|,则|A|=|B|,换言之,如果存在一对一函数f从A到B和g从B到A,则存在A和B之间的一一对应函数。

    可计算与不可计算:如果存在某种编程语言写的计算机程序能计算该函数的值,则称为是可计算的,如果一个函数不是可计算的,就说是不可计算的。

    矩阵

    布尔运算

    0-1矩阵的并和交:矩阵的对应位进行并和交

    A=[101010],B=[010110]AB=[100110011100]=[111110]AB=[100110011100]=[000010]

    布尔积:令A=[aij]m×k阶0-1矩阵,B=[bij]k×n阶0-1矩阵。A和B的布尔积,记为AB,是m×n矩阵[cij],其中

    cij=(ai1b1j)(ai2b2j)...(aikbkj)
    A=[100110],B=[110011]AB=[(11)(00)(11)(01)(10)(01)(01)(10)(01)(11)(00)(11)(11)(00)(11)(01)(10)(01)]=[110011110]

    令A为0-1方阵,r为正整数,A的r次布尔幂是r个A的布尔积,记作A[r],因此

    A[r]=AA...A

    算法

    算法

    搜索

    直接搜索:略

    二分搜索:伪代码

    排序

    冒泡排序和插入排序

    字符串匹配算法

    朴素字符串匹配算法

    贪婪算法

    安排讲座的贪婪算法:如果我们在每一步选择那个与巳选讲座相容的讲座中结束时间最早的讲 座,我们就能安排最多的讲座。

    procedure schedule(s1s2...sn:讲座开始时间,e1e2...en:讲座结束时间)

    根据结束时间对讲座排序,重新编号使得e1e2...en

    S:=

    for j := 1 to n

    if 讲座j与S相容 then

    S:=S{j}

    return S{S是已经安排讲座的集合}

    停机问题

    停机问题(halting problem):它询间是否存在一个过程(procedure) 能做这件事:该过程以一个计算机程序以及该程序的一个输入作为输入,并判断该程序在给定输入运行时是否最终能停止。

    这个问题是没有解的

    证明:假设停机问题有一个解,一个称为H(P,I)的过程。过程H(P,I)有两个输入项, 令一个是程序P,另一个是程序P的一个输入I。如果H判定P在给定输入I时能终止,则H(P,I)将产生字符串“停机”作为输出。反之,H(P,I)将产生字符串“无限循环”作为输出。现在我们将导出一个矛盾。

    编写一个过程的时候,它本身就表达为一个由字符构成的串,该串可以解释为一个比特序列。这意味着一个程序本身就可以当作数据使用。因此,一个程序可以作为另一个程序的输入,甚至是自身的输入。这样,H可以将一个程序P作为它的两个输入,即一个程序和该程序的输入。H应该可以判断当P给定其自身的副本作为输入时, P 是否会停机。

    为了证明不存在过程H能够求解停机问题,我们构造一个简单过程K(P),如果H(P, P) 的输出是“无限循环”,即P在自身作为输入时会无限循环,那么让K(P)停机。如果H(P,P)的输出是“停机”,即P在自身作为输入时会停机,那么让K(P)无限循环。即K(P)做出和 H(P,P) 的输出相反结果。

    image-20231022163505938

    现在假设把K作为K的输入。需要注意,如果H(K, K)的输出是“无限循环”,那么根据K的定义可以得出 K(K)停机。这意味着由H的定义, H(K, K)的输出是“停机”,这是一个矛盾。否则,如果 H(K, K) 的输出是“停机”,那么根据 K 的定义K(K)会无限循环,这意味着由H的定义, H(K, K) 的输出是“无限循环”。这也是一个矛盾。这样,H并不总能给出正确的答案。因此,没有这样的过程能解决停机问题。

    函数的增长

    大O记号

    定义:令f和g为从整数集或实数集到实数集的函数,如果存在常数C和k使得只要当x>k是就有

    |f(x)|C|g(x)|

    就可以说f(x)是O(g(x))的,读作f(x)是大Og(x)的。

    f(x)O(g(x))的,并且对于足够大的x有函数h(x)的绝对值大于g(x),则有f(x)O(h(x)),换言之,在f(x)O(g(x))的这一关系中的g(x)可以替换为具有更大绝对值的函数。

    如果|f(x)|C|g(x)|ifx>k,并且如果对所有x>k|h(x)|>|g(x)|,那么

    |f(x)|C|h(x)|ifx>k

    f(x)O(h(x))的。

    重要函数的大O估算

    定理1:令f(x)=anxn+an1xn1+...+a1x+a0,则f(x)O(xn)的。

    对于n!n!=123nnnnn=nn,所以n!O(nn)

    对于logn!logn!=lognn=nlogn,所以logn!O(nlogn)

    函数组合的增长

    定理2:假定f1(x)O(g1(x))的,f2(x)O(g2(x))的,那么(f1+f2)(x)O(g(x))的,其中对所有xg(x)=max(|g1(x)|,|g2(x)|)

    定理3:假定f1(x)O(g1(x))的,f2(x)O(g2(x))的,那么(f1f2)(x)O(g1(x)g2(x))的。

    Ω与大Θ记号

    令f和g为从整数集合或实数集合到实数集合的函数,如果存在正常数Ck使得当x>k时有

    |f(x)|C|g(x)|

    大O记号表示上界,大Ω记号表示下界

    令f和g为从整数集合或实数集合到实数集合的函数,如果f(x)O(g(x))的且f(x)Ω(g(x))的,则f(x)Θ(g(x))的。当f(x)Θ(g(x))时,就说f(x)是大西塔g(x)的,即f(x)g(x)阶的,即f(x)g(x)是同阶的。

    算法复杂度

    时间复杂度

    线性搜索算法的时间复杂度

    算法中每次循环都要做两次比较,一次in判断是否已到达列表结尾,一次xai比较元素x和列表中的一项。再加上一次比较用于退出循环和一次循环外的比较,最坏情况需要2n+2次比较,是Θ(n)的。

    二分搜索算法的时间复杂度

    假定列表一共有n=2k个元素,其中k是非负整数。k=logn(如果列表中元素个数n不是2的幂次,那么该列表可以看作一个有2k+1个元素的大列表的一部分。)

    在算法的每一阶段,都要比较i和j(分别是当前待搜索列表的第一项和最后项的位置)来判断待搜索列表是否包含一个以上的元素。如果i<j,则要做一次比较来判断是否大于待搜索列表的中间元素。

    第一阶段搜索限于含2k1个元素的列表,至此已经用了两次比较,下一阶段便是在2k2个元素的列表中循环,以此类推,当搜索到只剩下一个元素时,一次比较告诉我们列表中没有其他元素,再一次用于判断这一项是否为x,所以最多需要2k+2=2logn+2次比较,所以时间复杂度是Θ(n)

    冒泡算法的时间复杂度

    在每一遍冒泡排序都连续比较相邻元素,必要时交换相邻元素。当第i遍开始时,i1个最大的元素 保证在正确位置上。在这一遍,使用了ni次比较。冒泡排序对 n 个元素的列表进行排序时所需使用的总的比较次数是

    (n1)+(n2)++2+1=n(n1)2

    插入排序的时间复杂度

    插入排序把第j个元素插入到前j-1个已排好顺序的元素中的正确位置上。插入排序用线性搜索技术来做到这一点,依次比较第j个元素与后续各项,直到找到大于或等于这个元素的一项或者比较aj与它自身为止,因为aj不小于它自身。于是,在最坏情形下,把第j个元素插入正确位置需要j次比较。所以,用插入排序对n个元素的列表排序时所使用总的比较次数是

    2+3++n=n(n+1)21

    矩阵乘法的复杂度

    普通的方阵乘法复杂度为n3次乘法和n2(n1)次加法,但是有快速算法,只需O(n7)次乘法和加法

    一般性的矩阵相乘,如m1×m2矩阵和一个m2×m3矩阵相乘,需要做m1m2m3次整数乘法。

    理解算法的复杂度

    复杂度术语复杂度术语
    Θ(1)常量复杂度Θ(nb)多项式复杂度
    Θ(logn)对数复杂度Θ(bn),b>1指数复杂度
    Θ(n)线性复杂度Θ(n!)阶乘复杂度
    Θ(nlogn)线性对数复杂度  

    易解性:能用多项式最坏情形复杂度(或更优)的算法求解的问题称为易解的;

    难解性:不能用最坏情形多项式时间复杂度的算法解决的问题;

    P与NP:注意人们相信许多可解的问题具有这样的性质,即没有多项式最坏情形时间复杂度的算法能求解,但是一旦有了一个解答,却可以用多项式时间内来验证。能以多项式时间内验证解的问题称为属于 NP 类(易解的问题属于 P 类)。

    NP完全问题 (NP-complete problem):具有这样的性质即只要其中任何一个问题能用一个多项式时间最坏情形算法来求解,那么NP类的所有问题都能用多项式时间最坏情形算法来求解。可满足性问题也是NP完全问题的一个例子。

    P与NP问题(P versus NP problem):问NP(有可能在多项式时间内检验其解的一类问题) 是否等于P(一类易解的问题)。如果PNP,则存在这样一些不能在多项式时间内求解但其解 可以在多项式时间内验证的问题。NP完全性的概念有助于研究解决P与NP问题,因为NP完全问题是那些在NP类中被认为最不可能是P类中的问题,由于NP中的每个问题可以在多项式时间内归约为一个NP完全问题。绝大多数理论计算机科学家相信PNP,这意味着没有NP完全问题能在多项式时间内解决。

    数论和密码学

    整除性和模算术

    除法算法

    用记号a|b表示a整除b,当a不能整除b则写成ab,可以用量词将a|b写成(c(ac=b))。

    除法算法:a=dq+rq=adivdr=amodd

    如果ab为整数而m为正整数,则当m整除a-b时称a模m同余b,用记号ab(modm)表示,称其为同余式(congruence),m是模。如果a和b不是模m同余的,则写成ab(modm)

    模算术

    定理:令a和b为整数,并令m为正整数,则ab(modm)当且仅当amodm=bmodm

    定理:令m为正整数,整数a和b是模m同余的当且仅当存在整数k使得a=b+km

    定理:令m为正整数,如果ab(modm)cd(modm),则

    a+cb+d(modm)andacbd(modm)

    推论:令m是正整数,令a和b是整数,则

    (a+b)modm=((amodm)+(bmodm))modm

    并且

    abmodm=((amodm)(bmodm))modm

    模m算术

    可以再Zm,即小于m的非负整数的集合{0,1,,m1}上定义算术运算,

    整数加法:a+mb=(a+b)modm

    整数乘法:amb=(ab)modm

     

    整数表示和算法

    构造b进制的算法:

    procedure base b expansion (n,b:正整数且b>1) q:=n k:=0 while q0 ak:=qmodb q:=qdivb k:=k+1 return (ak1a1a0) {(ak1a1a0)b就是n的b进制展开式}

    求解div和mod的算法(python)

    快速模指数运算:计算bkmodm,注意到

    bn=ban12n1++a12+a0=ban12n1ba12ba0

    为了计算bn的值,只需计算b,b2,(b2)2=b4,,b2k1的值,一旦有了这些值,把列表aj=1那些项对应的b2j相乘。

    如计算311311=383231

    通过依次求出bmodm,b2modm,,b2k1modm,将其中aj=1的那些项b2jmodm相乘,在每次乘法后求乘积后求乘积除以m所得的余数。

    procedure modular exponentiation(b:整数, n=(ak1a1a0),m:正整数) x:=1 power:=bmodm for i:=0tok1 if ai=1 then x:=(xpower)modm power:=(powerpower)modm

    return x {x等于bnmodm}

    代码(python) rapidexp[快速模指数运算].py

    素数和最大公约数

    这里的很多内容在stein写的《Fouier analysis》这本书的狄利克雷定理那一章初等数论部分有,笔记见 数学.md #傅里叶分析 #狄利克雷定理。

    埃拉托斯特尼筛法:用来寻找不超过一个给定整数的所有素数。不超过 100 的合数必定有一个不超过 10 的素因子。因为小于 10 的素数仅有 2 、 3 、5 和 7, 所以不超过 100 的素数就是这四个素数以及那些大于 1 且不超过 100 同时不能被 2 、 3 、5 和 7 之一整除的正整数。

    一些猜想

    梅森素数:当p为素数时,2p1也为素数(很大的素数)

    素数定理:当x无限增长时,不超过x的素数个数与x/lnx之比π(x)趋近于1

    哥德巴赫猜想:每个大于5的奇数n都是三个素数之和(或者是每个大于2的偶数是两个素数之和,两者等价)。

    猜想(已被证明):存在无限多个可以写成n2+1形式的素数,其中n为正整数。

    孪生素数猜想:孪生素数是指相差2的一对素数,诸如3和5、5和7、11和13、17和19、4967和4969。孪生素数猜想断定存在无限多对孪生素数。关于孪生素数已被证明的最好结果是有无限多对p和p+2 ,其中p是素数,p+2是素数或者是两个素数乘积(陈景润在1966 年证明)。设 P(n) 为命题:存在无限多对差值恰为n的素数对。孪生素数猜想就是命题P(2)为真。研究孪生素数猜想的数学家设计了一个稍微弱一点的猜想,称为有界间隔猜想,声称存在一个N 使得 P(N) 为真。

    最大公约数:gcd(x,y) 最小公倍数:lcm(x,y)

    定理:令a和b为正整数,则ab=gcd(a,b)lcm(a,b)

    欧几里得算法

    procedure gcd(a,b:正整数) x:=a y:=b while y0 r:=xmody x:=y y:=r return x{gcd(a,b)是x}

    贝组定理:如果a和b为正整数,则存在整数st使得gcd(a,b)=sa+tb

    扩展欧几里得算法求解a和b的贝组系数

    设置s0=1,s1=0,t0=0,t1=1,令

    sj=sj2qj1sj1tj=tj2qj1tj1

    其中qj为欧几里得算法中求gcd(a,b)做除法时的商,即 q:=adivb

    ex_euclid[扩展欧几里得算法].py

    定理:令m为正整数,令a,b和c为整数。如果acbc(modm)gcd(c,m)=1,则ab(modm)

    求解同余方程

    线性同余方程

    线性同余方程:同余方程的形式为axb(modm),其中m为正整数,a和b为整数,而x为变量。

    怎样求解线性同余方程axb(modm)呢?即,如何能找出所有满足这一同余方程的整数x呢?我们要介绍的一个方法是利用使得a¯a1(modm)成立的整数a¯,如果这样的整数存在。这样的整数 a¯称为a模m的逆。当a和m互素时,下面的定理能保证a模m的逆存在。

    求解a模m的逆

    对于ab=1(modm),其中b就是a的逆元,可以利用贝组定理,得到

    ab+km=1

    注意这里用到了gcd(a,m)=1的条件,则可以通过扩展欧几里得算法求出b,即贝组系数中的s。

    定理(定理4.1):如果a和m为互素的整数且m>1,则a模m的逆存在。再者,这个模m的逆是唯一的。

    证明:如果a和m互素,则gcd(a,m)=1,根据贝组定理,存在整数s和t使得,sa+tm=1,则存在sa+tm1(modm),因为tm0(modm),所以有

    sa1(modm)

    因此,s为a模m的逆。

    假设有s1,s2满足条件,即存在s1a+t1m=1,s2a+t2m=1,两者相减得到(s1s2)a+(t1t2)m=0,则有(s1s2)a+(t1t2)m=0(modm),再有(s1s2)a=0(modm),因为a0(modm),所以s1s2=0,唯一性得证。

    中国剩余定理:令m1,m2,,mn为大于1的两两互素的正整数,而a1,a2,,an是任意整数,则同余方程组

    xa1(modm1)xa2(modm2)xan(modmn)

    有唯一的模m=m1m2mn的解。

    证明:令Mk=m/mk,当ikmimk没有大于1的公因子,可得gcd(mk,Mk)=1,由定理4.1可得,存在整数yk,即Mkmk的逆,使Mkyk=1(modmk),构造一个满足所有方程的解,取和

    x=a1M1y1+a2M2y2++anMnyn

    以第一个方程为例,因为Mk=0(modm1),k1,x中除了第一项都可以整除m1,而因为M1y1=1(modm1),所以第一项a1M1y1=a1(modm1),同理x是所有方程的解。

    举例:求解

    x2(mod3)x3(mod5)x2(mod7)

    使用构造法求解

    首先令m=357=105M1=m/3=35M2=m/5=21M3=m/7=15,可以看出2是M1=35模3的逆,因为352221(mod3);1是M2=21模5的逆,因为211(mod5);1 也是M3=15的模7逆,因为151(mod7)。该方程组的解是那些满足下列式子的x:

    x=a1M1y1+a2M2y2+a3M3y3=2352+3211+2151=233=23(mod105)

    从而得出 23 是方程组的最小正整数解。我们的结论是23是最小的正整数满足除以3时余2,除以 5 时余 3,除以 7 时余 2 。

    使用反向替换算法计算

    对于第一个方程x=3t+2,将x带入第二个方程可得

    3t+2=5m+33(at+b)+2=5m+33amod5=0(3b+23)mod5=(3b1)mod5=0

    由于3和5互素,所以a肯定为5,b可以通过搜索小于a的值即小于5得到b=2,所以解得t2(mod5),设t=5u+2,则x=15u+8,再带入第三个方程,通过类似方法得到u1(mod7)(15b+6%7=0,解得b=1),设u=7m+1,则x=105m+23,则最小正整数解为23。

    大整数的计算机算术

    假定m1,m2,,mn是两两互素的模数,并令m为其乘积。根据中国剩余定理可以证明满足0a<m的整数a可唯一地表示为一个n元组,其元素由a除以mi的余数组成,i= 1, 2, …, n 。即a 可以唯一地表示为

    (amodm1,amodm2,,amodmn)

    欲求 123 684 和 413 456 的和,根据中国剩余定理,每个小于 99 • 98 • 97 • 95 = 89403930的非负整数均可唯一地用该整数除以这四个模数的余数表示。例如,把123684表示为(33, 8, 9, 89),因为123684 mod 99=33,123684 mod 98=8, 123684 mod 97 =9 及 123684 mod 95=89。类似地,413456可表示为(32, 92, 42, 16) 。我们针对这些四元组而非直接针对这两个整数做运算,把四元组的对应分量相加,再按相应的模数压缩各分量。这样可得

    (33,8,9,89)+(32,92,42,16)=(65mod99,100mod98,51mod97,105mod95)=(65,2,51,10)

    要求出和,即(65,2,51,10)所表示的整数,需要求解同余方程组

    x65(mod99)x2(mod98)x51(mod97)x10(mod95)

    求解结果为537140,程序代码如下:

    费马小定理

    如果p为素数,a是一个不能被p整除的整数,则

    ap11(modp)

    再者,对每个整数a都有

    apa(modp)

    可以利用费马小定理计算整数高次幂的模p余数

    举例:计算7222mod11

    7222=72210+2=(710)2272=(1)2249=49mod11=5(mod11)

    伪素数

    许多素数n都可以满足2n11(modn),但不幸的是,存在合数(如n=341)使得该式成立,因此被称为以2为基数的伪素数。

    需要说明的是,不能通过选择足够多的基数来区分素数与伪素数,因为有些正整数能通过满足gcd(b, n)=1的基数的所有测试。

    一个正合数n如果对于所有满足gcd(b,n)=1的正整数b都有同余式bn11(modn)成立,称其为卡米切尔数

    举例:整数561是卡米切尔数,首先561=31117,如果gcd(b, 561)= 1,则gcd(b, 3)= gcd(b, 11)=g cd(b, 17)=1 。

    利用费马小定理可得到

    b21(mod3),b101(mod11),b161(mod17)

    b560=(b2)280=1(mod3)b560=(b10)56=1(mod3)b560=(b16)35=1(mod3)

    原根和离散对数

    模素数p的一个原根是Zp中的整数r,使得Zp中每个非零元素都是r的一个幂次。

    举例:判断2和3是否是模11的原根

    Z11中计算2的幂次时,可得21=2,22=4,23=8,24=5,25=10,26=9,27=7,28=3,29=6,210=1,因为Z11中的每个非零元素都是2的一个幂次,所以2是11的原根;

    反之计算3的幂次时,31=336=3重复了,所以不是原根。

    假设p是一个素数,r是一个模p的原根,而a是介于(含)1和p-1之间的一个整数,如果remodp=a0ep1,我们说e是以r为底a模p的离散对数,写作logra=e

    离散对数问题的输入是一个素数p、一个模p的原根 r 和一个正整数aZp,而输出是以 r为底 a 模p的离散对数。(在密码学中有用)

     

    同余的应用

    散列函数

    在实践中,会用到了许多不同散列函数,最常用的散列函数之一是

    h(k)=kmodm

    其中m是可供使用的内存地址的数目。

    举例:找出由散列函数h(k)=k mod 111分配给社会安全号为064212848和037149212的客户记录的内存地址

    h(064212848)=064212848mod111=14h(037149212)=037149212mod111=65

    所以社会安全号为064212848的客户记录被分配到内存地址14,而社会安全号为 037149212 的客户记录被分配到内存地址65。

    由于散列函数不是一对一的(因为很可能键值的数量大于内存地址数),所以有可能多个记录被分配到同一个内存地址。当这种情况发生时,就说出现了冲突。消解冲突的一个办法是使用散列函数分配但已被占用的地址后面第一个未占用的地址。

    伪随机数

    最常用的产生伪随机数的过程是线性同余法。我们选择4个整数:模数m、倍数a、增量c和种子x0,满足2a<m,0c<m0x0<m。通过连续应用下面递归函数来生成一个伪随机数序列{xn},满足对所有n,0xn<m

    xn+1=(axn+c)modm

    大部分计算机确实使用线性同余生成器来生成伪随机数,通常是使用增量c=0的线性同余生成器,这样的生成器称为纯倍式生成器。例如,以2311为模,以75=16807为倍数的纯倍式生成器就广为采用。采用这些参数,可以证明在重复之前会产生2312个数。

    校验码

    同余可用于检查数字串中的错误。在这样的字串中检错的一项常用技术就是在串的结尾处添加一个额外的数字。 这最后一个数字,或校验码,是用特定的函数来计算的。然后为了判定一个数字串是否正确,需要做一个检验看看这最后一位数字是否具有正确的值。如奇偶校验,通用产品代码和国际标准书号。

    密码学

    古典密码学

    换位密码

    举例:利用基于集合{1, 2, 3, 4}上的置换σ的换位密码,其中σ(1)=3,σ(2)=1,σ(3)=4,σ(4)=2

    加密明文消息 PIRAT E ATTACK

    首先将明文信息分为4个字母一组,则为 PIRA TEAT TACK。要加密每个分组,我们把第一个字母移到第三位,把第二个字母移到第一位,把第三个字母移到第四位,再把第四个字母移到第二位。得到IAPR ETTA AKTC。

    密码系统:是一个五元组(P,C,K,E,D),这里的P代表明文串的集合,C是密文串的集合,K是密钥空间(所以可能的密钥的集合),E是加密函数的集合,而D是解密函数的集合。用Ek表示在E中相对于密钥k的加密函数而Dk是D中用来解密由Ek加密的密文的解密函数,即对于所有明文串p

    Dk(Ek(p))=p

    公钥密码学

    所有古典密码,包括移位密码和仿射密码,都是私钥密码系统的实例。在私钥密码系统中,一旦你知道加密密钥,你就能很快找到解密密钥。所以,知道如何用一个特定的密钥加密消息就能让你解密用该密钥加密的消息。现代的私钥密码如AES已经非常复杂,被认为可以很好地抵御密码分析。可是,它仍然具有共享安全通信密钥的特性。再者,为了更加安全,双方每次通信会话都需要用一个新密钥,这就需要一种能生成并安全分享密钥的方法。

    为了避免每对希望安全通信的双方都需要共享密钥, 20 世纪 70 年代密码学家引入了公钥密码系统的概念。当使用这种密码系统时,知道怎样发送加密消息的人并不能解密消息。在这样的系统中,每个人都可以有一个众所周知的加密密钥。只有解密密钥是保密的,而且只有消息的预期接收人能解密。

    尽管公钥密码系统的优势是保密通信的双方不需要交换密钥,但其劣势是加密解密都会非常耗时。对许多应用而言,这将使得公钥密码系统变得不实用。在这种情形下,通常是私钥密码系统取而代之。然而,公钥密码系统仍可以用于密钥的交换过程。

    目前最常用的是RSA密码系统,在 RSA 密码系统中,每个人都有一个加密密钥(n,e),这里n=pq是一个由两个大素数,比如各有 300 位数字的p和q的乘积构成的模数,e是与(p1)(q1)互素的指数。

    RSA加密:为了用特定的密钥(n, e)对消息加密,首先将明文消息M翻译成整数序列。为此,可以先将每个明文字母翻译成两位数,正如在移位密码中所做的翻译,只有一点不同 。 即对于字母A到J增加开始的0,所以 A 被翻译为00,B 为 01,…,J为 09。然后,将这些两位数连接起来构成数字串。接下来,将这个串再分成 2N 位数字等长的分组,这里 2N 是一个大偶数使得2N 位数字的整数 2525… 25 不超过n。(必要时,可以在明文消息后填充无意义的 X 使得最后一组的大小和其他分组一样)

    经过这些步骤,我们已经将明文消息M翻译成了一个整数序列m1,m2,...,mk,k为整数。加密过程是将每个分组mi转换称密文分组ci,由下列函数实现

    C=Memodn

    RSA解密:已知解密密码d即e模(p1)(q1)的逆时(由于e与(p1)(q1)互素,所以逆肯定存在,见定理4.1),就可以很快地从密文消息恢复出明文消息。为了说明这一点,注意如果de1(mod(p1)(q1)),则有整数k使得de=1+k(p1)(q1)。由此可知

    Cd(Me)dMde=M1+k(p1)(q1)

    根据费马小定理,可得Mp11(modp)Mq11(modq),因此

    CdM(Mp1)k(q1)M1M(modp)

    CdM(Mq1)k(p1)M1=M(modq)

    由于gcd(p,q)=1,所以由中国剩余定理可得

    CdM(modpq)

    举例:使用RSA系统及密钥(2537, 13)对消息STOP加密,注意2537=43*59,p=43和q=59是素数,并且

    gcd(e,(p1)(q1))=gcd(13,4258)=1

    为了加密,先把STOP的字母翻译成等价的数字。然后按4位数字一组对这些数字分组(因为2525 <2537<252525),得到1819 1415,用下面的映射对每组加密

    C=M13mod2537=181913mod2537=2081C=M13mod2537=141513mod2537=2182

    对加密消息 2081 2182进行解密,d=937是13模42·58=2436的逆(93713=1(mod4258)),因此可以使用937作为解密指数。

    M=C937mod2537
    M12081937mod2537=1819M22182937mod2537=1415

    翻译成英文字母为STOP。

    为什么 RSA 密码系统适合作为公钥密码呢?首先,通过找寻两个各有300多位的大素数p和q,再找寻一个与(p1)(q1)互素的整数e,就可能迅速构造一个公钥。当知道模数n的因子分解,即知道素数p和q时,我们就可以迅速找到e模(p1)(q1)的逆d。(这可以利用欧几里得算法寻找d和(p1)(q1)的贝祖系数s和t来完成,这表明d模(p-1)(q-1)的逆是smod(p1)(q1)),有了d就使得我们可以解密用加密密钥发送的消息。可是,没有一种已知的解密方法不是基于寻找n的因子分解式的,或者说也不导致n的因子分解。

    一个简单的RSA程序: simpleRSA[一个简单的RSA程序].py

    同态加密

    全同态密码系统:是否有这样一个密码系统,允许在加密数据上做任何计算并能够产生由该非加密输入所得的非加密输出的加密形式。有了这样的密码系统,就不需要解密数据了,因为程序可以在远端系统上运行而不必解密输入或输出数据。

    RSA是乘法同态的,而不是加法同态,所以是偏同态。

     

    归纳与递归

    数学归纳法

    基本原理

    数学归纳法原理:为证明对所有的正整数n,P(n)为真,其中P(n)是一个命题函数,需要完成两个步骤:

    基础步骤:证明命题P(1)为真

    归纳步骤:证明对每个正整数,蕴含式P(k)P(k+1)为真

    可以描述为:(P(1)k(P(k)P(k+1)))nP(n)

    一些例子

    举例:使用数学归纳法证明7n+2+82n+1能被57整除

    基础步骤:P(0)=57能被57整除

    归纳步骤:假设P(k)成立,对于P(k+1)有

    P(k+1)=7(k+1)+2+82(k+1)+1=77k+2+6482k+1=7(7k+2+82k+1)+5782k+1

    显然能被57整除

    举例:证明排讲座的算法(贪婪算法按照结束时间排)的最优

    基础步骤:设贪婪算法在主讲座厅只安排一个讲座t1。这意味着任何其他讲座都不能在t1的结束时间e1或之后进行了。否则,根据讲座结束时间非降序顺序的要求,就应该存在一个讲座,它应该在t1讲座之前进行。因此,在e1时刻,每个剩余的讲座都要求使用讲座厅,因为它们都要求在e1时刻或e1时刻之前开始,并在e1时刻之后结束。这就导致了主讲座厅不能安排两个讲座,因为它们都要求在e1时刻使用讲座厅。这就证明了P(1)为真,基础步骤证毕。

    归纳步骤:需要证明P(k)为真的假设下,当需要选择k+1个讲座时,贪婪算法也总是安排了最多的讲座。现在假定算法已经选择了k+1个讲座。要完成归纳步骤的第一步是:证明存在一个包含讲座t1且安排了最多讲座的计划表,其中t1代表最先结束的那个讲座。容易看出,由于一个开始于讲座ti(i>1)的计划表是可以改变的,使得t1成为第一个讲座。为了说明这一点,注意:因为e1ei,所以ti之后的讲座仍然可以被安排。一旦包含了讲座t1,计划表就可以归结为:在e1时刻或e1之后,安排尽可能多的讲座。因此,如果已经安排了尽可能多的讲座,那么除了讲座t1之外,以t1结束时开始的计划表就是原始计划表的一个最优安排。这是因为贪婪算法在建立这个计划表时已经安排了k个讲座,根据归纳假设,当算法安排k+1个讲座时,它已经安排了最多的讲座。因此,P(k+1)也为真。这就完成了归纳步骤。

    举例:有奇数个人站在一个院子里,彼此之间的距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人。利用数学归纳法证明:人群中至少有一个幸存者,即至少有一个人没有被馅饼攻击。

    命题:当2n+1个人站在院中,彼此之间距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人时,至少存在一个幸存者。为了证明此结果,将证明对所有的正整数n,P(n)为真。这是可行的,因为当n取遍所有正整数时,2n+1则取遍了所有大于等于3的奇数。注意,一个人的馅饼战斗是不存在的,因为不存在另外一个人成为他攻击的对象。

    基础步骤:n=1时一共有3个人站在院子中,彼此之间距离不同,假设距离最近的两个人是A和 B,而C是第三个人。因为三人中两两之间的距离是不同的,A与C之间的距离以及B与C之间的距离都不同于且大于A与B之间的距离,因此,C不会受到馅饼的攻击。这表明,三个人中至少有一个人不会受到馅饼的攻击。

    归纳步骤:假定P(k)为真,即当2k+1个人站在院中,彼此之间距离不同,每个人都同时用一个馅饼抛向并击打离他最近的人时,至少存在一个幸存者。当P(k+1)时,有2k+3个人站在院中,假设A和B是靠得最近的两个人,所以抛击时A和B相互抛击。分成两种情况

    (1)有人向A和B抛击:由于有人向A和B抛击,并且A和B相互抛击,所以A和B加起来至少会受到3个馅饼的抛击,那就代表至少有一个人没有被抛击(2k+1个人至少需要2k+1个馅饼才能全部抛击,现在最多只有2k个馅饼);

    (2)没人向A和B抛击:这样就退化成P(k)的情况,即至少有一个人不会受到馅饼的攻击。

    综上,P(k+1)时,至少有一个人不会受到馅饼的攻击

     

    强归纳法与良序性

    强归纳法

    在强归纳法中,归纳步骤需要证明的是:如果对所有不超过k的正整数而言,P(j)为真,那么 P(k+1)也为真,即关于归纳假设,假定对j=1,2,...,k而言,P(j)为真。

    强归纳法:为证明对所有的正整数n,P(n)为真,其中P(n)是一个命题函数,需要完成两个步骤:

    基础步骤:证明命题P(1)为真

    归纳步骤:证明对所有正整数k来说,蕴含式[P(1)P(2)P(k)]P(k+1)为真

    强归纳法有时也称为数学归纳法第二原理,或称为完全归纳法。当使用“完全归纳法”这一术语时,数学归纳法原理就称为不完全归纳法。

    利用强归纳法可以证明出数学归纳法不能轻易证明出来的结论

    举例:设我们能到达无限高梯子的第1个和第2个阶梯,且知道如果我们能到达某个阶梯,那么就能到达高出两阶的那个阶梯。我们能用数学归纳法证明“我们能到达每一个阶梯”吗?我们又能用强归纳法证明“我们能到达每一个阶梯”吗?(下面的证明只关注归纳步骤)

    数学归纳法:归纳假设是命题“我们能到达第k个阶梯”。为了能完成归纳步骤,需要证明:如果假定归纳假设是对正整数k而言的,也就是说,如果假定我们能够到达第k个阶梯,那么就能证明我们能到达第k+1个阶梯。然而,并没有明显的方式来完成这一归纳步骤,这是因为从所给信息来看,我们不知道是否能从第k个阶梯到达第k+1个阶梯。毕竟我们只知道“如果我们能到达一个阶梯,则我们能到达高出两阶的那个阶梯”。

    强归纳法:归纳假设是命题“我们能到达前k个阶梯中的每个阶梯”。为了能完成归纳步骤,需要证明:在归纳假设为真的情况下,即如果我们能到达前k个阶梯中的每个阶梯,那么我们就能到达第k+1个阶梯。已经证明了我们能到达第2个阶梯。这里只需注意:只要k>2,那么就可从第k-1个阶梯到达第k+1个阶梯,因为知道我们可以从某个阶梯到达高出两阶的那个阶梯。这样就由强归纳法完成了归纳步骤。

     

    利用强归纳法证明的例子

    只要对强归纳法稍加改变,就可以处理更为广泛的一类问题。特别是在强归纳步骤只对大于某个特定的整数有效时,可以改变强归纳法来适应这种情况。设b是一个固定的整数,而j是一个固定的正整数。如果能完成如下两个步骤,那么强归纳法就可以断言:对所有nb的整数n而言,P(n)为真。 基础步骤:验证命题P(b),P(b+ 1),...,P(b+j)为真。 归纳步骤:证明对所有kb+j的整数而言,[P(b)P(b+1)P(k)] P(k+1)为真。

    举例:若n是大于1的整数,则n可以写成素数之积

    基础步骤:P(2)为真,因为2可以写成一个素数之积,即它自身。

    归纳步骤:假定对所有满足2jk的正整数j来说P(j)为真。即假设对于大于等于2并不大于k的正整数,可以写成素数积的形式。要完成归纳步骤,就必须证明在这个假定下P(k+1)为真。有两种要考虑的情形,即k+1是素数和k+1是合数。若k+1是素数,则立即看出P(k+1)为真。否则,k+1是合数并且可以写成满足2ab<k+1的两个整数a和b之积。因为a和 b是大于等于2并不大于k的正整数,所以根据归纳假设(所有满足2jk的正整数j来说P(j)为真),a和b都可以写成素数之积。因此,若k+1是合数,则它可以写成素数之积,即在a的因子分解中的那些素数与在b的因子分解中的那些素数之积。

    举例:考虑一种游戏,其中两名选手轮流从两堆火柴中的一堆取出任意正整数的火柴。取走最后一根火柴的选手获胜。证明:如果开始时两堆火柴的数目相同,则第二名选手总是可以 保证获胜。

    基础步骤:当n=1时,先拿火柴的选手只有一种选择,从某一堆中取走一根火柴,剩下一堆只有一根,第二名选手可以取走这根火柴而获胜。

    归纳步骤:假设对所有1jk的j来说,P(j)为真,也就是说,只要游戏开始时两堆各有j根火柴,其中1jk,第二名选手就总是可以获胜。需要证明P(k+1)为真,开始时每堆火柴都有k+1根火柴,且在P(j)(j=1,2,...,k)为真的条件下,第二个选手获胜。当一开始第一个人先抽,那么就有两种情况,第一种情况,只拿了一部分,那么第二个人也只拿和第一个人相同数量的火柴,这样问题就会退化成1jk,这样第二个人肯定能获胜。第二种情况,第一个人拿走了全部的火柴,那么第二个人只需要拿走所有的火柴就能获胜了。

     

    计算几何学中使用强归纳法

    定理:具有n条边的简单多边形能够被三角形化成n-2个三角形,其中n3

    使用强归纳法证明该定理时,需要用到下面的引理(引理证明略)

    引理:每个简单的至少四边的多边形都存在一条内部对角线。

    基础步骤:T(3)为真,因为具有三条边的多边形是一个三角形。不需要对一个三角形加入任何对角线。该三角形已经被三角形化了,即它自身。 归纳步骤:关于归纳假设,假定对所有3jk的j而言,T(j)为真。也就是说,假定只要3jk,就能将具有j条边的简单多边形三角形化为j-2个三角形。为了完成归纳步骤,必须证明:当归纳假设为真时,T(k+1)为真,也就是说,具有k+1条边的任意简单多边形都能被三角形化为(k+1)-2=k-1个三角形。 因此,假定有一个具有k+1条边的简单多边形P。因为k+14,所以由引理1,P中存在一条内部对角线ab。现在,ab将P分成了两个简单多边形Q和R,且Q有s条边,R有t条边。Q和R的边都是P的边,还有一条边ab, 它是Q和R的公共边。注意由于Q和R都至少比P少一条边(因为它们都是由P通过去掉至少两条边,同时增加了对角线ab而形成的),因此有3sk3tk。此外,P的边数比Q和R的边数之和少两条,因为P的每条边要么是Q的一条边,要么是R的一条边,但不能既是Q的一条边又是R的一条边,而对角线ab是Q和R的一条公共边,但却不是P的一条边。即,k+1=s+t2 根据归纳假设,由于3sk3tk都成立,所以可以将Q和R分别三角形化为s-2个和t-2个三角形。其次,注意Q和R的三角形化合在一起构成了P的一个三角形化。(在Q和R中加入的每个对角线都是P的一条对角线。)因此,可以将P三角形化为总数为(s-2)+(t-2)=s+t-4=(k+1)-2个三角形,这就完成了强归纳法的证明。

     

    利用良序性证明

    良序性公理断言:任意一个非空的非负整数集合都有最小元素。我们将会看到,良序性公理是怎样直接应用于证明中的。此外,可以证明:良序性公理、数学归纳法原理以及强归纳法之间是等价的。

    举例:用良序性证明整除算法。回忆一下,整除算法说:若a是整数且d是正整数,则存在唯一的整数q和r满足0r<d和a=dq+r。

    设S是形如a—dq的非负整数的集合,其中q是整数。这个集合非空,因为-dq可以任意大(取q是绝对值很大的负整数)。根据良序性,S有最小元r=adq0。整数r非负且r<d。若不是这样,则S里存在更小的非负整数,即ad(q0+1)。为了看出这一点,假设rd。因为 a=dq0+r,所以ad(q0+1)=(adq0)d=rd0。因此,存在满足0r<d的整数r和q。

    唯一性的证明:假设存在r1r2q1q2满足条件,则在形如adq的非负整数的集合中存在两个最小元素,如果这两个不相等,就会出现悖论,所以r1=r2,对应的q1=q2

     

    递归定义与结构归纳法

    定理(拉梅定理):设a和b是满足ab的正整数,则欧几里得算法为了求出gcd(a,b)而使用的除法的次数小于或等于b的十进制位数的5倍。

    证明:当使用欧几里得算法求满足ab的gcd(a,b)时,有下面的等式(a=r0b=r1

    r0=r1q1+r20r2<r1r1=r2q2+r30r3<r2rn2=rn1qn1+rn0rn<rn1rn1=rnqn

    这里为了求rn=gcd(a,b)而使用了n次除法,注意商q1,q2,...,qn1都至少是1,另外qn2,因为rn<rn1。这就蕴含了

    rn1=f2rn12rn2f2=f3rn2rn1+rnf3+f2=f4r2=r3+r4fn1+fn2=fnb=r1r2+r3fn+fn1=fn+1

    fn是一个斐波那契数列,满足fn+1>an1,其中a=(1+5)/2。得出b>an1

    log10b>(n1)log10a>(n1)/5

    因此,n1<5log10b,现在假定b有k个十进制位。则b<10klog10b<k,由此得出n1<5k,而且因为k是整数,所以得出n5k

     

    结构归纳法

    基础步骤:证明对于递归定义的基础步骤所规定的属于该集合的所有元素来说,结果成立。 递归步骤:证明如果对于定义的递归步骤中用来构造新元素的每个元素来说命题为真,则对于这些新的元素来说结果成立。

    举例:可以定义关于T、F、s命题变量以及集合{¬,,,,}中运算的复合命题的合式公式的集合。现在证明每个合式公式都含有相等个数的左括号和右括号

    基础步骤:公式T、F和s每个都不包含括号,所以显然它们含有相等个数的左括号和右括号。

    递归步骤:假设p和q都是各自含有相等个数的左括号和右括号的合式公式。换句话说,如果lplq分别是p和q中左括号的个数,rprq分别是p和q中右括号的个数,则lp=rplq=rq。为了完成归纳步骤,需要证明(¬p),(pq),(pq),(pq),(pq)也各自含有相等个数的左括号和右括号。这些复合命题中第一个的左括号的个数等于lp+1,其他每个复合命题的左括号个数等于lp+lq+1。同样,这些复合命题中第一个的右括号个数等于rp+1,其他每个复合命题的右括号个数等于rp+rq+1。因为lp=rplq=rq,所以这些复合表达式每个都含有相等个数的左括号和右括号。

     

    递归地定义满二叉树T的高度h(T)

    基础步骤:只含有树根r的满二叉树T的高度是h(T)=0

    递归步骤:如果T1T2都是满二叉树,则满二叉树T=T1T2有高度h(T)=1+max(h(T1),f(T2))

     

    定理:如果T是满二叉树,则n(T)2h(T)+11

    基础步骤:对于只含有树根r的满二叉树来说,结果为真,因为n(T)=1并且h(T)=0,所以

    n(T)=120+11=1

    归纳步骤:对于归纳假设,假定当T1T2都是满二叉树,n(T1)2h(T1)+11并且n(T2)2h(T2)+11。根据n(T)h(T)的递归公式,有n(T)=1+n(T1)+n(T2)h(T)=1+max(h(T1),f(T2))

    n(T)=1+n(T1)+n(T2)1+(2h(T1)+11)+(2h(T2)+11)2max(2h(T1)+1,2h(T2)+1)122h(T)1=2h(T)+11

    广义归纳法

    略(原书315页)

     

    递归算法

    定义:若一个算法通过把问题归约到带更小输入的相同问题的实例来解决原来的问题,则称这个算法是递归的。

    递归计算最大公约数

    procedure gcd(a,b:非负整数且a<b) if a=0 then return b else return gcd (b mod a, a) {输出是gcd(a, b)}

    递归模指数的算法

    procedure mpower(b, n, m:整数且m2n01b<m) if n=0 then return 1

    else return b*mpower(b, n-1, m) mod m

    {输出是bnmodm}

    分类讨论n奇偶性

    procedure mpowerbetter(b, n, m:整数且m2n01b<m) if n=0 then return 1

    else if n是偶数 then

    return mpower(b,n/2,m)2 mod m

    else

    return [(mpower(b,n/2,m)2 mod m) (b mod m)]mod m

    {输出是bnmodm}

    上述算法的python代码见 recursive1[递归计算的一些实例].py

     

    归并排序

    归并排序首先通过不断地把表一分为二来把表分成单个的元素,用归并排序算法排序每个子表,然后合并这两个子表。

     

    递归归并排序

    procedure mergesort (L=a1,...,an) if n>1 then m:=n/2 L1:=a1,..,am L2:=am+1,...,an L:=merge(mergesoft(L1),mergesort(L2)) {现在L中的元素以非降序排列}

    归并两个表

    procedure merge(L1L2:已排序的表) L := 空表 while L1L2都非空 L1L2的第一元素中较小的元素所在的表中删除这个元素并且把这个元素放到L的左端 if 删除这个元素导致一个表为空 then 从另一个表中删除所有元素并且把这些元素附加到L的后面 return L{L是元素按照递增顺序排列的已归并的表}

    python代码: mergesort[归并排序].py

    归并排序的时间复杂度为O(nlogn)

     

    程序正确性

    定义:若当对一个程序或程序段S的输入值来说初始断言p为真时,就有对S的输出值来说终结断言q为真,则说S是相对于p和q部分正确的。记号p{S}q说明程序或程序段S是相对于初始断言p和终结断言q部分正确的。

    推理规则

    合成规则:

    p{S1}qq{S2}rp{S1;S2}r

    计数

    鸽巢原理

    定理:如果k+1个或更多的物体放入k个盒子,那么至少有一个盒子包含了2个或更多的物体。

    推论:一个从有k+1甚至更多个元素的集合到k个元素的集合的函数f不是一对一函数

    证明:设函数f陪域中的每一个元素y都有一个盒子,包含了定义域中满足f(x)=y的x。因为定义域有k+1或者更多个元素,而陪域只有k个元素,所以由鸽巢原理可知这些盒子中有一个包含了定义域中2个或者更多的x元素,这说明f不是一对一函数。

    举例:对每个整数n,存在一个数是n的倍数且在它的十进制表示中只出现0和1

    令n是正整数,考虑n个整数1,11,111,...,111(在这个表中,最后一个整数的十进制表示中具有n+1个1)。注意当一个整数被n整除时存在n个可能的余数,因为这个表中有n+1个整数,由鸽巢定理,必有两个整数在除以n时有相同的余数。这两个整数之差的十进制表示中只含有0和1,且它能被n整除。

    广义鸽巢原理

    定理:如果N个物体放入k个盒子,那么至少有一个盒子包含了至少N/k个物体。

    举例:在100个人中至少有100/12=9个人生在同一个月。

     

    鸽巢原理的简单应用

    举例:证明在不超过2n的任意n+1个正整数中一定存在一个正整数被另一个正整数整除

    把n+1个整数a1,a2,...,an+1中的每一个都写成2的幂与一个奇数的乘积。换句话说,令aj=2kjqj(j=1,2,,n+1),其中kj是非负整数,qj是奇数。整数q1,q2,,qn+1都是小于2n的正奇数。因为只存在n个小于2n的正奇数,所以必然会存在qi=qj,因此也就能得到aiaj之间能整除。

    定理:每个由n2+1个不同实数构成的序列都包含一个长为n+1的严格递增子序列或严格递减子序列

    证明:令a1,a2,...,an2+1n2+1个不同实数的序列,与序列中的每一项ak相关联着一个有序对,即(ik,dk),其中ik是从ak开始的最长的递增子序列的长度,dk是从ak开始的最长的递减子序列的长度。

    假定没有长为n+1的递增或递减子序列,那么ikdk都是小于或等于n的正整数,那么(ik,dk)的有序对一共有n2中可能。而一共有n2+1个有序对,所以必有两个有序对相等,而这是不可能的。假设相等的两项序号分别为s和t(t>s),由于各项不相同,以as>at为例,则对于as而言,小于at的数肯定也小于as,再加上at本身,所以ds肯定大于dt,产生矛盾,所以肯定包含一个长为n+1的严格递增子序列或严格递减子序列。

     

    拉姆齐数R(m,n)(m和n都是大于或等于2的正整数)表示:假设晚会上每两个人是朋友或者是敌人,那么在一个晚会上使得或者有m个人两两都是朋友,或者有n个人两两都是敌人所需要的最少人数。

    已知R(3,3)=6,R(4,4)=18,对于拉姆齐数,当3mn时,我们只知道9个数的精确值

    一些性质:R(2,n) = n,R(m,n)=R(n, m)

     

    排列和组合

    排列数:P(n,r)=n!(nr)!

    组合数:C(n,r)=n!r!(nr)!

     

    二项式系数和恒等式

    定理:设x和y是变量,n时非负整数,那么

    (x+y)n=j=0n(nj)xnjyj=(n0)xn+(n1)xn1y++(nn1)xyn1+(nn)yn

    推论:设n为非负整数,那么

    k=0n(nk)=k=0nn!k!(nk)!=2n

    推论:设n为非负整数,那么

    k=0n(1)n(nk)=0

    帕斯卡恒等式和三角形

    定理:设n和k是满足nk的正整数,那么有

    (n+1k)=(nk1)+(nk)

    其他二项式系数恒等式

    定理(范德蒙德恒等式):设m,n和r是非负整数,其中r不超过m或n,那么

    (m+nr)=k=0r(nrk)(nk)

    定理:设n和r是非负整数,rn,那么

    (n+1r+1)=j=rn(jr)

    排列与组合的推广

    有重复的排列

    定理:具有n个物体的集合允许重复的r排列数是nr

    有重复的组合

    定理:n个元素的集合中允许重复的r组合有C(n+r-1,r)=C(n+r-1,n-1)个。

    举例:方程 x1+x2+x3=11的解,其中x1x2x3是非负整数。

    这个解对应从一个三元素集合中选11个元素的方式,假设这里有11个元素(它们加起来就是11),现在要添加2个分割线将它们分为三个集合,所以可以假设一共有13个元素,挑两个位置放分割线,所以一共是C(13, 2)=C(n+r-1, n-1)=78。

    给变量加上限制如x11x22x33,这样一来相当于只有11-(1+2+3)=5个元素让我们选了,所以一共有C(3+5-1, 2)=21种选择方式。

     

    具有不可区别的物体的集合的排列

    定理:设类型1的相同的物体有n1个,类型2的相同的物体有n2个,...,类型k的相同的物体有nk个,那么n个物体的不同排列数是

    n!n1!n2!nk!

    举例:重新排列单词SUCCESS中的字母能构成多少个不同的串

    计算:7!2!3!=420

     

    后续内容不过多介绍

     

    生成排列和组合

    生成排列

    生成n个最小正整数的排列,然后用对应的元素替换这些整数。已经建立了许多不同的算法来生成这个集合的n!个排列。我们将要描述的算法是以{1,2,3,...,n}的排列集合上的字典顺序为基础的。按照这个顺序,如果对于某个k,1kna1=b1a2=b2,...,ak1=bk1,并且ak<bk,那么排列a1a2...an在排列b1b2...bn的前边。换句话说,如果在n个最小正整数集合的两个排列不等的第一位置,一个排列的数小于第二个排列的数,那么这 个排列按照字典顺序排在第二个排列的前边。

    举例:在362541后面按照字典顺序下一个最大的排列是什么?

    解:使得aj<aj+1的最后一对整数ajaj+1a3=2a4=5,排列在2右边大于2的最小整数为a5=4,因此将4放在第三个位置。然后整数2、5和1按递增顺序放置,即364125。

     

    按字典顺序生成下一个最大排列

    procedure next_permutation(a1a2an: {1,2,...,n}的排列,不等于n...1) j := n—1 while aj>aj+1 j := j—1 {j是使得aj<aj+1的最大下标} k := n while aj>ak k := k-1 {ak是在aj右边大于aj的最小整数} 交换ajak r := n s := j + 1 while r>s 交换aras r := r-1 s := s+1 {这把在第j位后边的排列尾部按递增顺序放置} {现在a1a2an是下一个排列}

    生成排列的python代码: gen_permutation[生成排列].py

     

    生成组合

    可以利用一个集合(包括n个元素)的子集与n位比特串之间的对应关系

    举例:找出在1000100111后面的下一个最大的比特串

    解:相当于(1000100111+1)2=1000101000,下一个最大的比特串位为1000101000

     

    离散概率

    概率论

    生日问题

    如果要求房间内至少有2个人有相同生日的概率大于1/2,那么所需的最少人数是多少?

    为了找到房间内n个人至少2个人生日相同的概率,可以一个一个的来看,先看第一个人进入房间,那么他肯定不会与别人生日相同,第二个人进入房间,生日不相同的概率是365/366,第三个人生日互不相同的概率为364/366,第j个人进入房间后与其他人生日都不相同的概率为(366-(j-1))/366,假设生日相互独立,那么j个人生日互不相同的概率为:

    pn=365366364366367n366

    则至少有两个人生日相同的概率为1pn,可以确定最少人数为23人。

    另外一种算法:先算所有人生日都不相同,假设有n个人,一共有366个生日,所以n个人一共有366n中可能,全部不相同,从366天里面选择n天(n<=366,如果n大于366,根据鸽巢原理,则必有两个人生日相同),这样有CNn种可能,再将这些生日排列出来,一共有n!种排列方式,所以生日互不相同的概率为:

    pn=CNnn!366n=N!(Nn)!366n

    那么至少有两个人生日相等的概率为1-pn

    生日问题的仿真: birthday[生日问题].py

     

    举例:散列函数碰撞的概率

    令m为有效地址的个数,关键字的个数为n个(k1,k2,...,kn),则n个关键字被映射到不同地址的概率为

    pn=m1mm2mmn+1m

    概率方法

    定理:如果k是一个整数,k≥2,那么R(k,k)2k/2,R(k,k)是拉姆齐数。

     

    期望值和方差

    定理(比安内梅公式):如果X和Y是样本空间S上两个独立的随机变量,那么V(X+Y)=V(X)+V(Y),这里的V(X)表示X的方差。对于正整数n,Xi是S上两两独立的随机变量,i=1,2,...,n,那么

    V(X1+X2++Xn)=V(X1)+V(X2)++V(Xn)

    定理(切比雪夫不等式):设X是在样本空间S上的概率函数为p的随机变量。如果r是一个正实数,那么

    p(|X(s)E(X)|r)V(X)/r2

    证明:设A是事件A={s∈S||X(s)-E(X)|≥r},注意到

    V(X)=sS(X(s)E(X))2p(s)=sA(X(s)E(X))2p(s)+sA(X(s)E(X))2p(s)

    这个表达式中的第二个和是非负的,因为它的每个被加数是非负的,又因为对于每个元素s,有

    (X(s)E(X))2r2,所以这个表达式的第一个和至少为sAr2p(s),因此

    V(X)sAr2p(s)=r2p(A)

    所以p(A)V(X)/r2

     

    高级计数技术

    递推关系的应用

    用递推关系构造模型

    举例:汉诺塔问题,将n个盘子从A处搬到B处,还有C处可作为中间点暂存盘子,在A、B、C三处都只能允许从上到下按照从小到大的顺序排列。问总共需要多少次操作完成目标。

    使用递推思想,将n-1个盘子从A处搬到C处(B处作为中间点)需要Hn1次操作,再将A处的最后一个盘子(也是最大的)搬到B处,再将暂存在C处的盘子搬到B处(A处作为中间点),还是需要Hn1次操作,所以最后需要2Hn1+1次操作,即

    Hn=2Hn1+1=2(2Hn2+1)+1=22Hn2+2+1=22(2Hn3+1)+2+1=23Hn4+22+2+1=2n1H1+2n2++22+2+1=2n1+2n2++22+2+1=2n1

    汉诺塔问题的python代码如下:

     

    举例:对于不含2个连续0的n位比特串的个数,找出递推关系和初始条件。有多少个这样的5位比特串?

    当比特串以1结尾时有hn1个这样的比特串,当比特串以0结尾时,则倒数第二位必然为1,则有hn2个这样的比特串,即

    hn=hn1+hn2

    h1=2h2=3h5=13

    举例:编码字的枚举,如果一个十进制数字串包含偶数个0,计算机系统就把它作为一个有效的编码字。例如,1230407869是有效的,而120987045608不是有效的。设an是有效的n位编码字的个数,找出一个关于an的递推关系。

    注意a1=9,除了0之外都满足要求。假设已经有了一个n-1位编码字,此时在后面加上一个数字:

    第一种情况,无效字符串加了0就可以得到n位有效的字符串,n-1位的字符串一共有10n1种,所以无效的字符串个数为10n1an1

    第二种情况,有效字符串加了非0,一共有9an1种加法

    所以an=9an1+10n1an1=8an1+10n1

    还可以通过定义一个无效字符串个数vn,当n位字符串最后一位非0,则有9an1种加法;最后一位为0时,则有vn1种加法;可以得到an=9an1+vn1。同样也可以得到无效字符串个数的迭代公式vn=9vn1+an1,联立也可解出上面的迭代公式。

     

    算法与递推关系

    动态规划实例:对于安排讲座的问题,现在我们的目标不是安排尽可能多的讲座,而是尽可能多地合并已规划讲座的参与者。设有n个讲座,讲座j开始于时间tj结束于时间ej,有wj个学生参与。我们需要规划最大的参与学生人数,即我们希望规划一组讲座使得在所有安排的讲座中wj之和最大。(注意,当一个学生参与了多个讲座时,这个学生通过他参与的讲座数来计数。)

    我们用T(j)来表示由一个优化调度得到的前j场讲座的最大参与总数,T(n)就是一个优化调度得到的对于所有n个讲座的最大参与总数。首先将讲座结束时间升序排序。此后,我们重新编号讲座,e1e2en。我们说两个讲座是相容的当它们能成为一个规划的一个部分,即它们的时间不会重叠。(不同于一个结束而同时另一个开始。)对于eisj,我们定义p(j)为最大整数i,i<j,如果这个整数存在;否则p(j)=0。这样,如果存在,讲座p(j)是与讲座j相容的在讲座j前结束的结束最晚的讲座。否则p(j)=0,这样的讲座不存在。

    为了设计一个解决这个问题的动态规划算法,我们首先提出一个关键的递推关系。首先注意j≤n。对于前j个讲座,有两种可能的优化调度(注意,我们已经将n个讲座按结束时间升序排序)(i)讲座j属于优化调度;(ii)它不属于。

    情况(i):我们知道讲座p(j)+1,...,j-1不可能属于这个规划,因为这些讲座与讲座j都不相容。进一步,在优化调度中的其他讲座必定包括了讲座1,2,...,p(j)的一个优化调度。因为如果对于1,2,...,p(j)有更好的优化调度,通过加上讲座j,我们将得一个比总体 优化调度更好的规划。所以,在情况(i)下,T(j)=wj+T(p(j))

    情况(ii):当讲座j不属于一个优化调度时,讲座1,2,...,j的优化调度就与讲座1,2,...,j-1的一样。因此,在情况(ii)下,T(j)=T(j-1)。结合情况(i)和(ii),可得到一个递推关系:

    T(j)=max(wj+T(p(j)),T(j1))

    调度讲座的动态规划算法

    Procedure Maximum_Attendees(s1,s2,...,sn:讲座的开始时间;e1,e2,...,en:讲座的结束时间;w1,w2,...,wn:讲座的参与人数)

    将讲座按结束时间排序,并重新标记讲座,保证e1e2en for j:= 1 to n if 没有任务i(i<j)与任务j相兼容; p(j)=0 else p(j) := max{i|i<j 并且任务i与任务j相兼容} T(0):=0 for j:= 1 to n T(j) := max(wj + T(p(j)), T(j-1)) return T(n) {T(n)是最大的参与人数}

     

    求解线性递推关系

    一个常系数的k阶线性齐次递推关系是形如

    an=c1an1+c2an2++ckank

    求解常系数线性齐次递推关系

    定理:设c1c2是实数,假设r2c1rc2=0有两个不相等的根r1r2,那么序列{an}是递推关系an=c1an1+c2an2的解,当且仅当an=a1r1n+a2r2n,n=(0,1,2,...),a1a2是常数。

    定理:设c1c2是实数,假设r2c1rc2=0只有一个根r0,那么序列{an}是递推关系an=c1an1+c2an2的解,当且仅当an=a1r0n+a2nr0n,n=(0,1,2,...),a1a2是常数。

    求解常系数线性非齐次递推关系

    定理:如果{an(p)}是常系数线性非齐次递推关系an=c1an1++ckank+F(n)的一个特解,那么每个解都是{an(p)+an(h)}的形式,其中{an(h)}是相伴的其次递推关系

    an=c1an1++ckank

    的一个解。

     

    分治算法和递推关系

    分治递推关系:f(n)=af(n/b)+g(n)

    二分搜索:f(n)=f(n/2)+2

    归并排序:f(n)=2f(n/2)+n

    举例:整数的快速乘法,有一种快速的乘法算法把每个2n位的二进制整数分成两块,每块n位。然后,原来2n位的二进制整数的乘法被分解成3个n位二进制数的乘法,还要加上移位和加法。

    假设a和b是两个整数的2n位的二进制表达式(为了使它们等长,如果需要,可以在这些表达式前面加上若干个0)。令

    a=(a2n1a2n2...a1a0)2,b=(b2n1b2n2...b1b0)2

    a=2nA1+A0b=2nB1+B0

    其中

    A1=(a2n1...an+1an)2,A0=(an1...a1a0)2B1=(b2n1...bn+1bn)2,B0=(bn1...b1b0)2

    快速整数乘法算法是基于恒等式

    ab=(22n+2n)A1B1+2n(A1A0)(B0B1)+(2n+1)A0B0

    分治递推关系:f(2n)=3f(n)+C(n)

     

    定理:设f是满足递推关系 f(n)=af(n/b)+c的增函数,其中n被b整除,a≥1,b是大于1的整数,c是一个正实数,那么

    f(n)={O(nlogba)a>1O(logn)a=1

    而且,当n=bk(其中k是正整数),a≠1时,f(n)=C1nlogba+C2,其中C1=f(1)+c/(a-1)且C2=-c/(a-1)。

     

    定理(主定理):设f是满足递推关系

    f(n)=af(n/b)+cn4

    的增函数,其中n=bk,k是一个正整数,a≥1,b是大于1的整数,c和d是实数,满足c是正的且b是非负的,那么

    f(n)={O(nd)a<bdO(ndlogn)a=bdO(nlogba)a>bd

    最近对问题(不多赘述)

     

    生成函数

    实数序列a0,a1,...,ak,...的生成函数是无穷级数

    G(x)=a0+a1x++akxk+=k=0akxk

    幂级数的有用事实

    定理:令f(x)=k=0akxkg(x)=k=0bkxk,那么

    f(x)+g(x)=k=0(ak+bk)xkandf(x)g(x)=k=0(j=0kajbkj)xk

    定理(广义二项式定理):设x是实数,|x|<1,u是实数,那么

    (1+x)u=k=0(uk)xk

    有用的生成函数表见P473-474页。

     

    计数问题与生成函数

    示例:求e1+e2+e3=17的解的个数,其中e1e2e3是非负整数,满足2≤e1≤5,3≤e2≤6,4≤e3≤7。

    上述限制解的个数为(x2+x3+x4+x5)(x3+x4+x5+x6)(x4+x5+x6+x7),则解的个数等于展开式中x17的系数。

     

    示例:使用生成函数求出从n类不同的物体中选择r个物体并且每类物体至少选1个的方式数。

    因为我们需要每类物体至少选1个,所以这n个类中的每类物体都对序列{ar}的生成函数G(x)贡献了因子(x+x2+x3+),其中{ar}是从n类不同的物体中选择r个物体并且每类物体至少选1个的方式数。因此

    (x+x2+x3+)n=xn(1+x+x2+)n=xn/(1x)n

    根据广义多项式有

    G(x)=xn/(1x)n=xn(1x)n=xnr=0(nr)(x)r=xnr=0(1)rC(n+r1,r)(1)rxr=r=0C(n+r1,r)xn+rlett=n+r=t=nC(t1,tn)xt

    使用生成函数求解递推关系

    举例:求递推关系ak=3ak1,k=1,2,3,...且初始条件a0=2

    G(x)=k=0akxk,注意到xG(x)=k=0akxk+1=k=1ak1xk,使用递推关系有

    G(x)3xG(x)=k=0akxk3k=1ak1xk=a0+k=1(ak3ak1)xk=2

    所以G(x)=2/(13x),通过生成函数表可以找到ak=23k

     

    使用生成函数证明恒等式

    举例:使用生成函数证明,n为正整数

    k=0nC(n,k)2=C(2n,n)

    首先C(2n,n)是(1+x)2nxn那一项的系数,同时有

    (1+x)2n=[(1+x)n]2=[C(n,0)+C(n,1)x+C(n,2)x2++C(n,n)xn]2

    在这个展开式中,xn那一项的系数是C(n,0)C(n,n)+C(n,1)C(n,n-1)+...+C(n,n)C(n,0)

    k=0nC(n,k)2=C(2n,n)

     

    容斥原理的应用

    Ai是具有性质Pi的元素的子集,具有所有这些性质的元素Pi1,Pi2,...,Pik的元素数将记为N(Pi1Pi2Pik)。用集合的术语写这些等式,有

    |Ai1Ai2Aik|=N(Pi1Pi2Pik)

    如果不具有n个性质Pi1,Pi2,...,Pik中的任何一个的元素数记为N(P1P2Pn),集合中的元素数记为N,那么有

    N(P1P2Pn)=N|Ai1Ai2Aik|

    由容斥原理有

    N(P1P2Pn)=N1inN(Pi)+1i<jnN(PiPj)1i<j<knN(PiPjPk)++(1)nN(P1P2Pn)

    举例:方程 x1+x2+x3=11的解,其中x1x2x3是非负整数,且x13x34x36

    (1)使用容斥定理,令解的性质P1x1>3,性质P2x2>4,性质P3x3>6,满足不等式x13x24以及x36的解的个数是

    N(P1P2P3)=N1i3N(Pi)+1i<j3N(PiPj)1i<j<k3N(PiPjPk)

    其中N表示解的总数即C(3+11-1,2)=78(详细分析见 有重复的组合

    N(P1)=(具有x1≥4的解数)=C(3+7-1, 2)=36

    其它以此类推。最后结果为6

    (2)由于x13x34x36,可以将其看成从x1x2x3中抽取两个元素(2=3+4+6-11),由于每个元素都可以取到大于2的值,所以每个元素本身就可以抽取两个元素,一共有3种方法,此外还可选择从任意两个集合内抽取一个元素,还是有C(3,2)=3种方法,总共是6种方法。

     

    映上函数个数

    定理:设m和n是正整数,满足mn,那么存在

    nmC(n,1)(n1)m+C(n,2)(n2)m+(1)n1C(n,n1)1m

    个从m元素集合到n元素集合的映上函数。

    从m元素集合到n元素集合的映上函数是这样一种对应方式:它把定义域中的m个元素分配到n个不可辨别的盒子中,使得每个盒子都不是空的,然后将陪域中的n个元素中的每一个元素都与一个盒子相对应。这意味着从具有m个元素的集合到具有n个元素的集合的映上函数的个数,等于把m个可辨别的物体分配到n个不可辨别的盒子中,使得每个盒子都不空时的方法数乘以具有n个元素的集合的排列数。因此,从m个元素的集合到n个元素的集合的映上函数的个数为 n!S(m,s),其中 S(m,n)是6.5节中定义的第二类斯特林数。

    举例:把5项工作分给4个不同的雇员,如果每个雇员至少分配1项工作,问有多少种方式?

    由定理可知:共有

    45C(4,1)35+C(4,2)25C(4,3)15=1024972+1924=240

    错位排列

    错位排列指将元素随机打乱并保证没有一个元素在原始位置。

    定理:n元素集合的错位排列数为

    Dn=n![111!+12!13!++(1)n1n!]

    证明:如果排列保持元素i不变,就设排列有性质Pi。错位排列的个数就是对i=1,2,...,n,没有性质Pi的排列数,即Dn=N(P1P2Pn),通过容斥定理可以看成全排列n!减去固定至少1个元素不变的错位排列,加上至少2个元素不变的错位排列...,至少一个1个元素的错位排列:C(n,1)(n-1)!(选一个固定住,全排列剩下的),至少2个元素的错位排列:C(n,2)(n-2)!,带入可证明。

     

    关系

    关系及其性质

    定义:设A和B是集合,一个从A到B的二元关系是A×B的子集。

    定义:集合A上的关系是从A到A的关系

    设集合A = {1,2,3,4},那么R={(1,1),(1,2),(2, 1),(2,2),(3,4),(4,1),(4,4)}就是一种关系

    定义:若对每个元素a∈A,有(a,a)∈R,那么定义在集合A上的关系是自反的。

    定义:对于任意a,b∈A,若只要(a,b)∈R就有(b,a)∈R,则称定义在集合A上的关系R为对称的。对于任意a,b∈A,若(a,b)∈R且(b,a)∈R,一定有a=b,则称定义在集合A上的关系R为反对称的。

    定义:若对于任意a,b,c∈A,(a,b)∈R并且(b,c)∈R则(a,c)属于R,那么定义在集合A上的关系R称为传递的。

    定义:设R是从集合A到B的关系,S是集合B到C的关系,R和S的合成是由有序对(a,c)的集合构成的关系,其中a∈A,c∈C,并且存在一个b∈B的元素,使得(a,b)∈R且(b,c)∈S,用SR表示R与S的合成。

    定义:设R是集合A上的关系,R的n次幂Rn(n=1,2,3,...)递归地定义为

    R1=RandRn+1=RnR

    定理:集合A上的关系R是传递的,当且仅当对n=1,2,3,...有RnR

     

    n元关系及其应用

    A1,A2,,An是集合,定义在这些集合上的n元关系是A1×A2××An的子集,这些集合A1,A2,,An称为关系的域,n称为关系的阶。

    数据库和关系

    当n元组的某个域的值能够确定这个n元组时,n元关系的这个域就叫作主键。这就是说,当关系中没有两个n元组在这个域有相同的值时,这个域就是主键。在一个n元关系中,域的组合也可以唯一地标识n元组。当一组域的值确定一个关系中的n元组时,这些域的笛卡儿积就叫作复合主键。

    n元关系运算

    定义:设R是一个n元关系,C是R中元素可能满足的一个条件。那么选择运算符sc将n元关系R映射到R中满足条件C的所有n元组构成的n元关系。

    定义:投影Pi1,i2,...,im,其中i1<i2<<im,将n元组(a1,a2,...,an)映射到m元组(ai1,ai2,...,aim),其中m≤n。换句话说,投影Pi1,i2,...,im删除了n元组的n-m个分量,保留了第i1i2,...,im个分量。对于一个表格而言就是删除了对应的列,并且将相同行合并。

    定义:连接运算符Jp将m元组的后p个分量与n元组的前p个分量相同的第一个关系中的所有m元组和第二个关系的所有n元组组合起来产生了一个新的关系。对于表格而言就是把两个表格相同行连接在一起,形成一个行数相等,列数增加的表格。

     

    数据挖掘中的关联规则

    如果将数据挖掘的场景局限在超市事务上,那么

    事务:客户在访问商店期间购买的一些商品的集合,如{牛奶、鸡蛋、面包}

    项集:商店里的每一件商品称为项,项的集合称为项集,k项集是一个包含恰好k项的项集。

    定义:在事务集合T={t1,t2,...,tk}中,其中k是正整数,项集I的计数记为σ(I),是包含在该项集中的事务数。项集I的支持度,是I包含在从T中随机选择的食物中的概率,即

    support(I)=σ(I)|T|

    对于特定的应用,会指定一个支持度阈值s。频繁项集挖掘是寻找支持度大于等于s的项集I的过程,这些项集被称为频繁项集。

    举例:一个事务集如下

    image-20231027104516207

    对于苹果而言,一共出现在了8个事务中的5个,所以σ(I)=5,支持度为5/8。

    关联规则的强度是根据它的支持度(包含I和J的事务频率)以及置信度(包含J时也包含I的事务频率)来衡量的。

    定义:若I和J是事务集T的子集,则

    support(IJ)=σ(IJ)|T|

    confidence(IJ)=σ(IJ)σ(I)

    关联规则IJ的支持度,即包含Ⅰ和J的事务的分数,是一个有用的度量。因为低支持度值告诉我们,包含I中所有项和J中所有项的项集是很少被购买的:而高支持度值告诉我们,它们是在很大一部分事务中被一起购买的。注意,关联规则IJ的置信度是已知一个事务包含I中的所有项,它将包含I和J中所有项的条件概率。因此,IJ的置信度越大,J成为包含I的事务的子集的可能性就越大。

     

    在上面的例子中,关联规则的支持度是 σ({苹果酒,甜甜圈} U {苹果})/|T|。因为σ{苹果酒,甜甜圈}U{苹果})=σ{苹果酒,甜甜圈,苹果})= 3,|T|=8, 可得这条规则的支持度是 3/8=0.375。 该规则的置信度是σ({苹果酒,甜甜圈} U {苹果})/σ({苹果酒,甜甜圈}) = 3/4=0.75。

     

    关系的表示

    关系矩阵:关系R可以用矩阵M表示,其中

    mij={1(ai,bj)R0(ai,bj)R

    对于关系的合成SR,根据布尔积的定义,有

    MSR=MRMS

    关系的闭包

    定义:设R是集合A上的关系,若存在关系R的具有性质P的闭包,则此闭包是集合A上包含R的具有性质P的关系S,并且S是每一个包含R的具有性质P的A×A的子集。

     

    有向图中的路径

    在有向图G中,从a到b的一条路径是图G中一条或多条边的序列

    定义:在有向图G中,从a到b的一条路径是图G中一条或多条边的序列(x0,x1),(x1,x2),(x2,x3),...,(xn1,xn),其中n是一个非负整数,x0=ax1=b。即一个边的序列,其中一条边的终点和路径中下一条边的始点相同。这条路径记为x0x1x2,...,xn1xn,长度为n。我们把一个为空的边的集合看作从a到a的长度为0的路径。在同一顶点开始和结束的长度n≥1的路径,称为回路或圈。

    定理:设R是集合A上的关系,从a到b存在一条长为n(n为正整数)的路径,当且仅当(a,b)∈Rn

    使用数学归纳法证明,当n=1时,(a,b)∈R,从a到b有一条长为1的路径

    假设对于正整数n成立,从a到b存在一条长为n+1的路径,当且仅当存在元素c∈A使得从a到c存在一条长为1的路径,即(a,c)∈R,以及一条从c到b的长为n的路径,即(c,b)∈Rn。因此,由归纳假设,从a到b存在一条长为n+1的路径,当且仅当存在一个元素c,使得(a,c)∈R 且(c,b)∈Rn。但是若存在这样一个元素,当且仅当(a,b)∈Rn+1。因此,从a到b存在一条长为n+1的路径,当且仅当(a,b)∈Rn+1。定理得证。

     

    传递闭包

    定义:设R是集合A上的关系,连通性关系R由形如(a,b)的有序对构成,使得在关系R中,从顶点a到b之间存在一条长度至少为1的路径。

    因为Rn由有序对(a,b)构成,使得存在一条从顶点a到b的长为n的路径,所以R是所有Rn的并集,即R=n=1Rn

    定理:关系R的传递闭包等于连通性关系R

    定理:设MR是定义在n个元素集合上的关系R的0-1矩阵,那么传递闭包R的0-1矩阵是

    MR=MRMR2MRn

    计算传递闭包的过程

    procedure transitive_closure(M: n×n的0-1矩阵)

    A:=M

    B:=A

    for i:= 2 to n

    A := A M

    B := B A

    return B {B是表示R的0-1矩阵}

    该算法的运算复杂度为O(n4)

    沃舍尔算法

    沃舍尔算法的基础是构造一系列的0-1矩阵。这些矩阵是W0W1,...,Wn,其中W0=MR是这个关系的0-1矩阵,且Wk=[wij(k)]。如果存在一条从vivj的路径使得这条路径的所有内部顶点都在集合{v1v2,...,vk}(表中的前k个顶点)中,那么wij(k)=1,否则为0(这条路径的起点和终点可能在表中的前k个顶点的集合之外)。注意Wn=MR,因为MR的第(i,j)项是1,当且仅当存在一条从vivj的路径,且全部内部顶点都在集合中{v1v2,...,vn}(但这些就是有向图中的所有顶点)。

    举例:假设W0矩阵如下,求解W1

    W0=[0001101010010010]

    对于W1,如果存在一条从i到j的且只有1作为其内部顶点的路径,则W1的(i,j)项为1。注意因为所有长为1的路径没有内部顶点,所以仍旧可以使用这些路径(1->4, 2->1, 2->3, 3->1, 3->4, 4->3),注意2还有一条2->1->4的路径,内部节点仅有1,所以可以将(2,4)置为1,所以W1

    W1=[0001101110010010]

    Wk1Wk,存在一条从i到j的只以{1,2,...,k}中的顶点作为内部顶点的路径,当且仅当要么存在一条从i到j的且内部顶点是列表中前k-1个顶点的路径,要么存在从i到k的路径和从k到j的路径,且这些路径的内部顶点仅在列表中的前k-1个顶点中。这就是说,要么在k被允许作为内点之前从i到j已经存在一条路径,要么允许k作为内部顶点产生一条从i到k然后从 k到j的路径。

    第一种类型的路径存在当且仅当wij[k1]=1,第二种类型的路径存在当且仅当wik[k1]=1wkj[k1]=1,于是,wij[k]=1当且仅当或者wij[k1]=1或者wik[k1]=1wkj[k1]=1,即

    wij[k]=wij[k1](wik[k1]wkj[k1])

    沃舍尔算法

    procedure Warshall(M: n×n的0-1矩阵)

    W := M

    for k := 1 to n

    for i := 1 to n

    for j := 1 to n

    wij := wij(wikwkj)

    return W {W=[wij]是MR}

    该算法的时间复杂度为O(2n3)

     

    等价关系

    定义:等价关系:自反的、对称的和传递的

    定义:如果两个元素a和b由于等价关系而相关联,则称它们是等价的。记法a~b通常用来表示对于某个特定的等价关系来说,a和b是等价的元素。

     

    偏序

    定义:偏序:自反的,反对称的和传递的。集合S和定义在其上的偏序R称为偏序集,记作(S,R)。

    关键词:哈塞图、极大元、极小元、最大元、最小元、拓扑排序、格

    偏序不太清楚有什么用。拓扑排序好像可以用来排任务

     

    图的术语和几种特殊的图

    基本术语

    每条边都连接两个不同的顶点且没有两条不同的边连接一对相同顶点的图称为简单图,可能会有多重边连接同一对顶点的图称为多重图

    定义:若u和v是无向图G中的一条边e的端点,则称两个顶点u和v在G里邻接(或相邻)。这样的边e称为关联顶点u和v,也可以说边e连接u和v。

    定义:图G=(V,E)中,顶点v的所有相邻顶点的集合,记作N(v),称为顶点v的邻居。若A是V的子集,我们用N(A)表示图G中至少和A中一个顶点相邻的所有顶点的集合,所以N(A)=vAN(v)

    定义:在无向图中,顶点的度是与该顶点相关联的边的数目,例外的情形是,顶点上的环为顶点的度做出双倍贡献。顶点v的度表示成deg(v)。

    定理(握手定理):设G=(V,E)是有m条边的无向图,则2m=vVdeg(v)

    定理:无向图有偶数个度为奇数的顶点。

    定义:当(u,v)是带有有向边的图G的边时,说u邻接到v,或者说v从u邻接。顶点u称为(u,v)的起点,v称为(u,v)的终点,环的起点和终点是相同的。

    定义:在带有有向边的图里,顶点v的入度,记作deg(v),是以v作为终点的边数。顶点v的出度,记作deg+(v),是以v作为起点的边数(注意,顶点上的环对这个顶点的入度和出度的贡献都是1)。

    定理:设G=(V,E)是带有向边的图,每条边都有一个起点和终点,于是

    vVdeg(v)=vVdeg+(v)=|E|

    二分图

    定义:若把简单图G的顶点集分成两个不相交的非空集合V1V2,使得图中的每一条边都连接V1中的一个顶点与V2中的一个顶点(因此G中没有边连接V1中的两个顶点或V2中的两个顶点),则G称为二分图。当此条件成立时,称(V1,V2)为G的顶点集的一个二部划分。

    定理:一个简单图是二分图,当且仅当能够对图中的每个顶点赋予两种不同的颜色,并使得没有两个相邻的顶点被赋予相同的颜色。

    完全二分图Km,n是顶点集划分成分别含有m和n个顶点的两个子集的图,并且两个顶点之间有边当且仅当一个顶点属于第一个子集而另一个顶点属于第二个子集。图9显示了完全二分图K2,3K3,3K3,5K2,6

    image-20231027215916527

    二分图和匹配

    举例:假设1个组中有m个员工,需要完成n种不同的工作,其中m≥n。每个员工都受过相关培训,能够完成这n个工作中的1种或多种。我们希望可以为每个员工分配一个工作。为了完成这个任务,我们可以使用图为员工的能力建模。用顶点表示每一个员工和每一个工作,对于每个员工,在表示他和他受过培训的工作的顶点之间建立一条边。注意,这个图的顶点集合被划分为两个不相交的集合,员工的集合和工作的集合,而且每条边都连接着一个员工和一个工作。因此,这个图是二分图,划分是(E,J),其中E是员工的集合,J是工作的集合。下面我们考虑两种不同的场景。

    第一,假设1组有4个员工:Alvarez、Berkowitz、Chen和Davis。假设完成项目1需要做4个工作:需求、架构、实现和测试。假设Alvarez受过需求和测试的培训;Berkowit受过架构、实现和测试的培训;Chen受过需求、架构和实现的培训;Davis仅受过需求的培训。 第二,假设这个组中第2个小组也有4个员工:Washington、Xuan、Ybarra和Ziegler。假设完成项目2也需要和完成项目1一样完成相同的4种工作。假设Washington受过架构的培训;Xuan受过需求、实现和测试的培训;Ybarra受过架构的培训;Ziegler受过需求、架构和测试的培训。 为了完成项目1,我们必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。如图所示(其中蓝色线表示工作分配),我们可以通过给Alvarez分配测试、给Berkowitz分配实现、给Chen分配架构和给Davis分配需求来完成这个要求。

    image-20231027222716059

    为了完成项目1,我们必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。如图(a)所示(其中蓝色线表示工作分配),我们可以通过给Alvarez分配测试、给Berkowitz分配实现、给Chen分配架构和给Davis分配需求来完成这个要求。

    为了完成项目2,我们也必须为每个工作分配一个员工以保证每个工作都有员工来做并且没有员工分配的工作多于一个。但是这是不可能的,因为只有Xuan和Ziegler两个员工至少受过需求、实现和测试这3个工作之一的培训。因此,没有办法为这3个工作分配3个不同的员工且每个工作都能分配一个受过相关培训的员工。

    寻找一种把工作分配给员工的方法可以视为在图模型中寻求匹配,其中,在简单图G=(V,E)中的一个匹配M就是图中边集E的子集,该子集中没有两条边关联相同的顶点。换句话说,匹配是边的子集,假设{s,t}和{u,v}是匹配中不同的边,那么s、t、u和v是不同的顶点。若一个顶点是匹配M中的一条边的端点,则称该顶点在M中被匹配;否则称为未被匹配。包含最多边数的一个匹配称为最大匹配。在二分图G=(V,E)中的一个匹配M,其划分为(V1,V2),若V中的每个顶点都是匹配中的边的端点或|M|=|V1|,则称匹配M是从V1V2完全匹配。例如,在给员工分配工作的过程中,要把最多数量的工作分配给员工,我们可以在表示员工能力的图模型中求一个最大匹配。从工作集合到员工集合求一个完全匹配来把所有的工作都分配给员工。

    定理(霍尔婚姻定理):带有二部划分(V1,V2)的二分图G=(V,E)中有一个从V1V2的完全匹配当且仅当对于V的所有子集A,有|N(A)|≥|A|,N(A)表示与A相邻的顶点的集合,这是完全匹配的充分必要条件。

    先来证明必要条件,假设从V1V2存在一个完全匹配M,那么若AV1,对于A中的每个顶点vA,在M中存在一条边连接v和V2中的一个顶点。因此,在V2中与V1中的顶点相邻的顶点的个数至少与V1中的顶点个数一样多。由此可得|N(A)|≥|A|。

    充分性通过强归纳法证明,比较困难,详见P580页。

     

    特殊类型图的一些应用

    举例:并行计算的互连网络,采用并行处理时,一个处理器需要另一个处理器产生的输出。因此这些处理器需要互连。

    最简单却又最昂贵的网络互连处理器,在每对处理器之间有一个双向连接。当有n个处理器时,这样的网络表示成n个顶点上的完全图Kn。当有64个处理器时,就需要C(64,2)=2016个连接,每个处理器都得直接连接到其他63个处理器。

    另一方面,互连n个处理器的最简单方式或许是使用称为线性阵列的排列方式。除了P1Pn以外的每个处理器Pi都通过双向连接与相邻处理器和Pi1Pi+1连接。P1只连接P2Pn只连接 Pn1。这种方式的缺点是为了让处理器共享信息,有时需要使用大量的称为跳(hop)的中间连接。6个处理器的线性阵列如下图所示:

    P1
    P2
    P3
    P4
    P5
    P6

     

    栅格网络(或二维阵列)是一种通用的互连网络。在这样的网络中,处理器个数是一个完全平方数,比方说n=m2。n个处理器标记成P(i,j),0≤i≤m-1,0≤j≤m-1。双向连接把处理器P(i,j)连接到它的4个相邻处理器P(i±1,j)和P(i,j±1),只要这些处理器是在栅格里。(注意,栅格角上的4个处理器只有2个相邻处理器,边界上其他处理器只有3个相邻处理器。有时也用每个处理器恰有4个连接的变种的栅格网络,栅格网络限制了每个处理器的连接数。某些成对处理器之间的通信需要O(n)=O(m)个中间连接。表示16个处理器的栅格网络如下图所示。

    image-20231027231141271

    超立方体是互连网络的一个重要类型。在这样的网络中,处理器个数是2的幂,n=2m。n个处理器标记成P0P1,...,Pn1,每个处理器都有到其他m个处理器的双向连接。连接到处理器Pi上的处理器,其下标的二进制表示与i的二进制表示恰恰有1位不同。8个处理器的超立方体网络如下图所示。

    image-20231027231410453

     

    从旧图构造新图

    定义:图G=(V,E)的子图是图H=(W,F),其中WVFE。若H≠G,则称图G的子图H是G的真子图 已知一个图的顶点集合,我们可以由图中的顶点和连接这些顶点的边得到这个图的子图。

    定义:令G=(V,E)是一个简单图。图(W,F)是由顶点集V的子集W导出的子图,其中边集F包含E中的一条边当且仅当这条边的两个端点都在W中。

    定义:两个简单图G1=(V1,E1)G2=(V2,E2)的并图是带有顶点集V1V2和边集E1E2的简单图。G1G2的并图表示成G1G2

     

    图的表示和图的同构

    有时,两个图具有完全相同的形式,从某种意义上就是两个图的顶点之间存在着一一对应,这个对应保持边的对应关系。在这种情形下,就说这两个图是同构的。

    邻接表:给出了与图中每个顶点相邻的顶点。

    邻接矩阵:若图G=(V(顶点),E(边))的邻接矩阵是A=[aij],其中

    aij={1{vi,vj}E0otherwise

    关联矩阵:若图G=(V,E)的关联矩阵是M=[mij],其中

    mij={1eivi0otherwise

    定义:设G1=(V1,E1)G2=(V2,E2)是简单图,若存在一对一的和映上的(从A到B的函数f称为映上的或满射的,当且仅当对每个b∈B,有元素a∈A使得f(a)=b)从V1V2的函数f,且f具有这样的性质:对V1中所有的a和b来说,a和b在G1中相邻当且仅当f(a)和f(b)在G2中相邻,则称G1G2是同构的。这样的函数f称为同构,两个不同构的简单图称为非同构的。

    换句话说,当两个简单图同构时,两个图的顶点之间具有保持相邻关系的一一对应。简单图的同构是一个等价关系。

     

    判定两个简单图是否同构

    判断两个简单图是否同构常常是一件困难的事情。在两个带有n个顶点的简单图的顶点集之间有n!种可能的一一对应。若n太大,则通过检验每一种对应来看它是否保持相邻关系是不可行的。 有时说明两个图不同构并不困难。特别是,如果能找到某个属性,两个图中只有一个图具有这个属性,但该属性应该在同构时保持,就可以说这两个图不同构。这种在图的同构中保持的属性称为图形不变量。例如,同构的简单图必须具有相同的顶点数,因为在这些图的顶点集之间有一一对应。

    举例:顶点数、边数以及顶点的度都是在同构下的不变量。若两个简单图的这些量有任何不同,则这两个图就不是同构的。不过,当这些不变量都相同时,也不一定意味着两个图是同构的。目前还没有已知的用来判定简单图是否同构的不变量集。

    举例:判断下面的图是否同构

    image-20231028082748003

    首先图G和H有相同的顶点数、边数以及顶点的度,然而G和H不同构。以G中的a点为例,对应了H中的t、u、x、y,而这四个顶点都与deg为2的顶点相邻,而G中的a点只与deg为3的顶点相邻。

    举例:判断图G和H是否是同构的

    image-20231028083725604

    G和H有着相同的顶点数、边数以及顶点的度,可以判断可能同构,再观察G中u1这个点,可以发现H中的v6v4对应,假设存在一个同构f使得f(u1)=v6,根据对应关系可以得到f(u2)=v3f(u3)=v4f(u4)=v5f(u5)=v1f(u6)=v2

    为了确定f是否保持边,可以检查G和H的邻接矩阵(此处的H矩阵使用G中的对应顶点的像来标记行和列),即此时H中的顶点为(v6->1,v3->2,v4->3,v5->4,v1->5,v2->6)。

    AG=[010100101001010100101010000101010010]AH=[010100101001010100101010000101010010]

    可以看到AG=AH,可以A和G同构。如果AGAH,则可以选择f(u1)=v4来判断是否同构。

    NAUTY是一种用于测试图同构的最佳使用算法。

     

    连通性

    通路

    定义:设n是非负整数且G是无向图。在G中从u到v的长度为n的通路是G的n条边e1,...,en的序列,其中存在x0=ux1,...,xn=v的顶点序列,使得对于i=1,...,n,eixi1xi作为端点。当这个图是简单图时,就用顶点序列x0x1,...,xn表示这条通路(因为列出这些顶点就唯一地确定了通路)。若一条通路在相同的顶点开始和结束,即u=v且长度大于0,则它是一条回路。把通路或回路说成是经过顶点x1x2,...,xn1或遍历边e1e2,...,en。若通路或回路不重复地包含相同的边,则它是简单的。

    定义:设n是非负整数且G是有向图。在G中从u到v的长度为n的通路是G的边的序列e1,...,en,使得f(e1)=(x0,x1)f(e2)=(x1,x2),...,f(en)=(xn1,xn),其中x0=uxn=v。当有向图中没有多重边时,就用顶点序列x0x1,...,xn表示这条通路。把在相同的顶点上开始和结束的长度大于0的通路称为回路或圈。若一条通路或回路不重复地包含相同的边,则把它称为简单的。

    定理:在连通无向图的每一对顶点之间都存在简单通路

     

    图是如何连通的

    有时删除图中的一个顶点和它所关联的边,就产生比原图具有更多连通分支的子图。把这样的顶点称为割点(或关节点)。从连通图里删除割点,就产生不连通的子图。同理,如果删除一条边,就产生比原图具有更多连通分支的子图,这条边就称为割边。注意,在表示计算机网络的图中,割点和割边表示了最重要的路由器和最重要的链路,为了使所有的计算机可以通信,它们不能发生故障。

    并不是所有的图都有割点,如完全连通图Kn,其中n≥3,就没有割点。不含割点的连通图称为不可分割图。若G-V'是不连通的,则称G=(V,E)的顶点集V的子集V'是点割集,或分割集。

    我们定义非完全图的点连通度为点割集中最小的顶点数,记作κ(G)。当 G 是完全图时,它没有点割集,因为删除它顶点集合的任意子集及其所有相关联的边后它仍然是一个完全图。同时,当G是完全图时,我们不能把κ(G)定义为点割集的最小顶点数。我们用κ(Kn)=n1来替代,这是需要删除的顶点数,以便得到只含有一个顶点的图。

    κ(G)≥k,我们称图为k连通的(或k顶点-连通的)。若图是连通的且不是只含1个顶点的图,则称该图是1连通的;若图是不可分割的且至少含有3个顶点,则称该图为2连通的或双连通的。注意若G是一个k连通图,则对所有的j,0≤j≤k,G是一个j连通图。

    与顶点类似,也有边割集边连通度(用λ(G)表示),若G是不连通的,则λ(G)=0。若G是只含有1个顶点的图,我们也定义λ(G)=0。由此可得,若G是含有n个顶点的图,则0≤λ(G)≤n-1。G 是含有n个顶点的图,λ(G)=n-1当且仅当G=Kn,这等价于命题,若G不是完全图,则λ(G)≤n-2

    对于所有的图而言,存在下面这个不等式

    κ(G)λ(G)minvVdeg(v)

    有向图的连通性

    定义:若对于有向图中的任意顶点a和b,都有从a到b和从b到a的通路,则该图是强连通的。

    定义:若在有向图的基本无向图中,任何两个顶点之间都有通路,则该有向图是弱连通的。

    有向图G的子图是强连通的,但不包含在更大的强连通子图中,即极大强连通子图,可称为 G 的强连通分支强分支。注意,若a和b是有向图中的两个顶点,它们的强连通分支或者相同或者不相交。

     

    通路与同构

    简单图的一个有用的同构不变量是长度为k的简单回路的存在性,其中k是大于2的正整数。

    举例:判定图G和图H是否是同构的

    image-20231028094825498

    G和H都具有6个顶点和8条边,各自具有4个度为3的顶点和2个度为2的顶点。所以对两个图来说,这3个不变量(顶点数、边数以及顶点度)都是相同的。但是H有长度为3的简单回路,即 v1v2v6v1。而通过观察可以看到,G没有长度为3的简单回路(G中的所有简单回路的长度至少为4)。因为存在一条长度为3的简单回路是一个同构不变量,所以G和H是不同构的。

     

    计算顶点之间的通路数

    定理:设G是一个图,该图的邻接矩阵A相对于图中的顶点顺序v1v2,...,vn(允许带有无向或有向边、带有多重边和环)。从vivj长度为r的不同通路的数目等于Ar的第(i,j)项,其中r是正整数。

    该定理可以用来求出在图的两个顶点之间的最短通路的长度,还可以用来判定图是否连通。

     

    欧拉通路与哈密顿通路

    欧拉通路与欧拉回路

    定义:图G中的欧拉回路是包含G的每一条边的简单回路。图G中的欧拉通路是包含G的每一条边的简单通路。

    定理:含有至少2个顶点的连通多重图具有欧拉回路当且仅当它的每个顶点的度都为偶数。

    构造欧拉回路

    procedure Euler(G:所有顶点的度都为偶数的连通多重图)

    circuit := 从G中任选的顶点开始,连续地加入边所形成的回到该顶点的回路 H := 删除这条回路的边之后的G while H还有边 subcircuit := 在既是H的顶点也是circuit的边的端点处开始的H的一条回路 H := 删除subcircuit的边和所有孤立点之后的H circuit := 在适当顶点上插入subcircuit之后的circuit return circuit {circuit是欧拉回路}

    定理:连通多重图具有欧拉通路但无欧拉回路当且仅当它恰有2个度为奇数的顶点。

     

    哈密顿通路与哈密顿回路

    定义:经过图G中每一个顶点恰好一次的简单通路称为哈密顿通路,经过图G中每一个顶点恰好一次的简单回路称为哈密顿回路。即,在图G=(V,E)中,若V={x0,x1,...,xn1,xn}并且对0≤i<j≤n来说有xixj,则图G中的简单通路x0x1,...,xn1xn称为哈密顿通路。在图G=(V,E)中,若x0x1,...,xn1xn是哈密顿通路,则x0x1,...,xn1xnx0(其中n>0)称为哈密顿回路。

    带有度为1的顶点的图没有哈密顿回路,因为在哈密顿回路中每个顶点都关联回路中的两条边。另外,若图中有度为2的顶点,则关联这个顶点的两条边属于任意一条哈密顿回路。此外注意,当构造哈密顿回路且该回路经过某一个顶点时,除了回路所用到的两条边以外,这个顶点所关联的其他所有边不用再考虑。而且,哈密顿回路不能包含更小的回路。

    定理(狄拉克定理):如果G是有n个顶点的简单图,其中n≥3,并且G中每个顶点的度都至少为n/2,则G有哈密顿回路。

    定理(欧尔定理):如果G是有n个顶点的简单图,其中n≥3,并且对于G中每一对不相邻的顶点u和v来说,都有deg(u)+deg(v)≥n,则G有哈密顿回路。

    已知最好的求一个图哈密顿回路或判定这样的回路不存在的算法具有指数级的最坏情形时间复杂度(相对于图的顶点数来说)。

     

    格雷码使得相邻的码具有恰好相差一位。可以这样找出格雷码:以下述方式列出所有长度为n的比特串,使得每一个串与前一个串恰好相差一位,而且最后一个串与第一个串恰好相差一位。可以用n立方体Qn来为这个问题建模。解决这个问题所需要的是Qn中的一条哈密顿回路。这样的哈密顿回路容易求出。例如,Q3的一条哈密顿回路显示在下图中。这条哈密顿回路所产生的前后恰好相差一位的比特串序列是000,001,011,010,110,111,101,100。

    image-20231028104420388image-20231028104828734

    左边表示Q3的哈密顿回路,右边(自己画的,不一定对)表示可以将其看成一个平面结构来求解哈密顿回路。

     

    最短通路问题

    最短通路算法

    迪杰斯特拉算法

    procedure Dijkstra(G:所有权都为正数的带权连通简单图)

    {G带有顶点a=v0,v1,...,vn=z和权w(vi,vj),其中若{vi,vj}不是G的边,则w(vi,vj)=} for i := 1 to n L(vi):= L(a) := 0 S := {现在初始化标记,使得a的标记为0而所有其余标记为∞,S是空集合} while zS u := a不属于S的L(u)最小的一个顶点 S := S U {u} for 所有不属于S的顶点 v if L(u)+w(u,v) < L(v) then L(v) := L(u)+w(u, v) {这样就给S中添加带最小标记的顶点,并且更新不在S中的顶点的标记) return L(z) {L(z)=从a到z的最短通路的长度}

    python代码: djikstra[迪杰斯特拉算法].py

    定理:迪克斯特拉算法使用O(n2)次运算(加法和比较)求出含有n个顶点的连通简单无向加权图中两个顶点之间最短通路的长度。

     

    弗洛伊德算法

    procedure Floyd(G:带权简单图) {G有顶点v0,v1,...,vn和权w(vi,vj),其中若(vi,vj)不是边,则w(vi,vj)=} for i := 1 to n for j := 1 to n d(vi,vj):=w(vi,vj) for i := 1 to n for j := 1 to n for k := 1 to n if d(vj,vi) + d(vi,vk) < d(vj,vk) then d(vj,vk) = d(vj,vi) + d(vi,vk) return d(vi,vj) {d(vi,vj)是在vivj之间的最短通路的长度,1≤i≤n,1≤j≤n}

     

    平面图

    定义:若可以在平面中画出一个图而边没有任何交叉(其中边的交叉是表示边的直线或弧线在它们的公共端点以外的地方相交),则这个图是平面图。这种画法称为这个图的平面表示。

    image-20231028123231793

    image-20231028123241980

    K3,3K5不是平面图。

     

    欧拉公式

    定理(欧拉公式):设G是带e条边和v个顶点的连通平面简单图。设r是G的平面图表示中的面数,则r=e-v+2

    举例:假定连通平面简单图有20个顶点,每个顶点的度都为3。这个平面图的平面表示把平面分割成多少个面?

    由题意可得 v=20,因为3×v=2×e(一条边有两个端点,而端点数对应所有顶点的度),所以e=30,r = e - v + 2 = 12

    推论:若G是e条边和v个顶点的连通平面简单图,其中v≥3,则e≤3v-6

    首先可以确定的是一个面的度数是大于或等于3的(一个三角形有3个顶点),所以有

    2e=rRdeg(r)3r(2/3)erev+2=r(2/3)ee3v6

    推论:若G是连通平面简单图,则G中有度数不超过5的顶点。

    假设G中的度数全部大于5,所以有2e≥6v,而e≤3v-6,所以存在矛盾,G中有度数不超过5的顶点。

    推论:若连通平面简单图有e条边和v个顶点,v≥3并且没有长度为3的回路,则e≤2v-4。

     

    库拉图斯基定理

    若一个图是平面图,则通过删除一条边{u,v}并且添加一个新顶点w和两条边{u,w}与{w,v}获得的任何图也是平面图,这样的操作称为初等细分。若可以从相同的图通过一系列初等细分来获得图G1=(V1,E1)和图G2=(V2,E2),则称它们是同胚的。

    image-20231028132212909

    定理:一个图是非平面图当且仅当它包含一个同胚于K3,3K5的子图。

    K3,3K5
    image-20231028133019540image-20231028133033298

     

    图着色

    定义:简单图的着色是对该图的每个顶点都指定一种颜色,使得没有两个相邻的顶点颜色相同。

    定义:图的着色数是着色这个图所需要的最少颜色数。图G的着色数记作χ(G)

    定理(四色定理):平面图的着色数不超过4。

    举例Kn的着色数为n(当n≥3时,已经不是平面图了)

    举例:完全二分图Km,n的着色数是2

    举例:图Cn(是一个圈图)的着色数,n是奇数且n≥3时,χ(Cn)=3,n是偶数且n≥4时,χ(Cn)=2

     

    图着色的应用

    举例:安排期末考试,使得没有学生同时要考两门,假设一共有7门课,用1-7来表示,不同的颜色表示不同时间段。

    image-20231028134534276

    定义:树是没有简单回路的连通无向图

    因为树没有简单回路,所以树不含多重边或环,因此任何树都必然是简单图。

    定理:一个无向图是树当且仅当在它的每对顶点之间存在唯一简单通路。

    定义:有根树是指定一个顶点作为根并且每条边的方向都离开根的树。

    定义:若有根树的每个内点都有不超过m个孩子,则称它为m叉树。若该树的每个内点都恰好有m个孩子,则称它为满m叉树。把m=2的m叉树称为二叉树。

    定理:带有n个顶点的树含有n-1条边。

    定理:带有i个内点的满m叉树含有n=mi+1个顶点。

    定理:一个满m叉树若有

    (1)n个顶点,则有i=(n-1)/m个内点和l=[(m-1)n+1]/m个树叶;

    (2)i个内点,则有n=mi+1个顶点和l=(m-1)i+1个树叶;

    (3)l个树叶,则有n=(ml-1)/(m-1)个顶点和i=(l-1)/(m-1)个内点。

    若一棵高度为h的m叉树的所有树叶都在h层或h-1层,则这棵树是平衡的。

    定理:在高度为h的m叉树中至多有mh个树叶。

    推论:若一棵高度为h的m叉树带有l个树叶,则hlogml。若这棵m叉树是满的和平衡的,则h=logml

     

    树的应用

    二叉搜索树

    二叉搜索树是一种二叉树,其中任何顶点的每个孩子都指定为右子或左子,没有顶点有超过一个的右子或左子,而且每个顶点都用一个关键字来标记,这个关键字是各元素中的一个。另外,这样指定顶点的关键字,使得顶点的关键字不仅大千它的左子树里的所有顶点的关键字,而且小千它的右子树里的所有顶点的关键字。

    若二叉搜索树是平衡的,则确定一个元素的位置或者添加一个元素所需要的比较次数不超过 log(n+1)次。

     

    决策树

    二叉搜索树可以用来基于一系列比较来找出元素的位置,其中每次比较都说明是否已经找到了元素的位置,或者是否应当向右或向左进入子树。其中每个内点都对应着一次决策,这些顶点的子树都对应着该决策的每种可能结果,这样的有根树称为决策树。问题的可能解对应着这个有根树中通向树叶的通路。

    n个元素的排序有n!种。

    定理:基于二元比较的排序算法至少需要logn!次比较。

    引理:基于二元比较的排序算法排序n个元素所用的比较次数是Ω(nlogn)

    定理:基于二元比较的排序算法排序n个元素所用的平均比较次数是Ω(nlogn)

     

    前缀码

    哈夫曼编码不过多赘述。

     

    博弈树

    博弈树的树叶表示游戏的终局。给每个树叶指定一个值,表示游戏在这个树叶所代表的局面终止时第一个选手的得分。对于非胜即负的游戏,用1来标记圆圈所表示的终结顶点以表示第一个选手获胜,用-1来标记方框所表示的终结顶点以表示第二个选手获胜。对于允许平局的游戏,用0来标记平局所对应的终结顶点。注意,对于非胜即负的游戏,为终结顶点指定值,这个值越高,第一个选手的结局就越好。

    定义:博弈树中顶点的值递归地定义为: (1)一个树叶的值是当游戏在这个树叶所表示的局面里终止时第一个选手的得分。 (2)偶数层内点的值是这个内点的孩子的最大值,奇数层内点的值是这个内点的孩子的最小值。

    使第一个选手移动到具有最大值的孩子所表示的局面并且第二个选手移动到具有最小值的孩子所表示的局面的策略称为最小最大策略

    定理:博弈树顶点的值说明,如果两个选手都遵循最小最大策略并且从博弈树的某一个顶点所表示的局面开始进行游戏,则这个顶点的值表明第一个选手的得分。

     

    树的遍历

    遍历算法

    常用的遍历算法有前序遍历、中序遍历和后序遍历

    定义(前序遍历):设T是带根r的有序根树。若T只包含r,则r是T的前序遍历。否则,假定T1T2,...,Tn是T的以r为根的从左向右的子树。前序遍历首先访问r,它接着以前序来遍历T1然后以前序来遍历T2,以此类推,直到以前序遍历了Tn为止。

    定义(中序遍历):设T是带根r的有序根树。若T只包含r,则r是T的中序遍历。否则,假定T1T2,...,Tn是T中以r为根的从左向右的子树。中序遍历首先以中序来遍历T1,然后访问r。它接着以中序来遍历T2,中序遍历T3,以此类推,直到以中序遍历了Tn为止。

    定义(后序遍历):设T是带根r的有序根树、若T只包含r,则r是T的后序遍历。否则,假定T1T2,...,Tn是T中以r为根的从左向右的子树。后序遍历首先以后序来遍历T1,然后以后序来遍历T2......然后以后序来遍历Tn,最后访问r。

     

    前序遍历

    procedure preorder(T: 有序根树)

    r := T的根

    打印r

    for 从左到右的r的每个孩子c

    T(c) := 以c为根的子树

    preorder(T(c))

    中序遍历

    procedure inorder(T:有序根树) r := T的根 if r 是树叶 then 打印r else i := 从左到右的r的第一个孩子 T(l) := 以l为根的子树 inorder(T(l)) 打印r for 除l外从左到右的r的每个孩子c T(c) := 以c为根的子树 inorder(T(c))

    后序遍历

    procedure postorder(T:有序根树)

    r := T的根

    for 从左到右的r的每个孩子c

    T(c) := 以c为根的子树

    postorder(T(c))

    打印r

    前序遍历对于内部顶点必须在叶子顶点前访问的应用来说是最佳选择,此外,前序遍历还用于复制二叉搜索树。后序遍历对于叶子顶点需要在内部顶点之前访问的应用来说是最佳选择。后序遍历在访问内部顶点之前访问叶子顶点,所以,它对于删除树是最佳选择,因为子树根顶点下面的顶点可以在子树的根顶点之前删除。拓扑排序是一种使用后序遍历实现的高效算法。

     

    中缀、前缀和后缀记法

    可以用有序树来表示复杂的表达式,比如复合命题、集合的组合,以及算术表达式。例 如,考虑由运算+(加)、-(减)、* (乘)、/(除)、↑(幂)所组成的算术表达式的表示。

    举例:((x+y)↑2) + ((x-4) / 3)的有序根树是什么

    image-20231028151807190

    上面这张图显示的是中缀形式,当以前序遍历表达式的有根树时,就获得它的前缀形式,写成前缀形式的表达式称为波兰记法。通过以后序遍历表达式的二叉树,就可以获得它的后缀形式,写成后缀形式的表达式称为逆波兰记法。

    前缀表达式和后缀表达式都是无二义性的。

     

    生成树

    定义:设G是简单图。G的生成树是包含G的每个顶点的G的子图。

    定理:简单图是连通的当且仅当它有生成树。

    深度优先搜索

    深度优先搜索的操作:任意选择图中一个顶点作为根。通过依次添加边来形成从这个顶点开始的通路,其中每条新边都与通路上的最后一个顶点以及还不在通路上的一个顶点相关联。继续尽可能地添加边到这条通路。若这条通路经过图的所有顶点,则由这条通路组成的树就是生成树。不过,若这条通路没有经过图中的所有顶点,则必须添加其他的顶点和边。退到通路中的倒数第二个顶点,若有可能,则形成从这个顶点开始的经过还没有访问过的顶点的通路。若不能这样做,则后退到通路中的另一个顶点,即在通路里后退两个顶点,然后再试。

    重复这个过程,从所访问过的最后一个顶点开始,在通路上一次后退一个顶点,只要有可能就形成新的通路,直到不能添加更多的边为止。因为这个图有有穷的边数并且是连通的,所以这个过程以产生生成树而告终。在这个算法的一个阶段上通路末端的顶点将是有根树中的树叶,而在其上开始构造一条通路的顶点将是内点。

    这个过程的本质是递归,若图中的顶点是排序的,则当总是选择在该顺序里可用的第一个顶点时,在这个过程的每个阶段上对边的选择就全都是确定的。不过,将不总是明显地对图的顶点排序。深度优先搜索也被称为回溯,因为这个算法返回以前访问过的顶点以便添加边。

    深度优先搜索

    procedure DFS(G: 带顶点v1,...,vn的连通图) T := 只包含顶点v1的树 visit(v1)

     

    procedure visit(v: G的顶点) for 与v相邻并且还不在T中的每个顶点w 加入顶点w和边{v,w}到T visit(w)

    计算复杂度为O(n2)

    宽度优先搜索

    从图的顶点中任意地选择一个根,然后添加与这个顶点相关联的所有边。在这个阶段所添加的新顶点成为生成树在第1层上的顶点,将新顶点任意排序。下一步,按顺序访问第1层上的每个顶点,只要不产生简单回路,就将与这个顶点相关联的每条边添加到树中。任意排序第一层的每个顶点的孩子,这样就产生了树在第2层上的顶点。遵循相同的过程,直到巳经添加了树中的所有顶点。因为在图中的边数是有限的,所以这个过程会终止。在产生了包含图中每一个顶点的树之后,生成树也就产生了。

    宽度优先搜索

    procedure BFS(G:带顶点v1,...,vn的连通图) T := 只包含顶点v1的树 L := 空表 v1放入尚未处理顶点的表L中 while L 非空 删除L中第一个顶点v for v 的每个邻居 w if w 既不在L中也不在T中 then 加入w到表L的末尾 加人w和边{v,w}到T

     

    回溯的应用

    举了图着色和n皇后的例子,不过多赘述

     

    有向图中的深度优先搜索

    可以轻而易举地修改深度优先搜索和宽度优先搜索,使得以有向图作为输入时它们也能运行。但是,输出不一定是生成树,而可能是森林。在这两个算法中,只有当一条边从正在访问的顶点出发并且到一个尚未加入的顶点时才加入这条边。如果在其中任何一个算法的某个阶段找不到从已经加入的顶点到尚未加入的顶点的边,则算法加入的下一个顶点成为生成森林中一个新树的根。

    举例:给定左图作为输入,深度优先搜索的输出是右图

    image-20231028154008845

    从顶点a开始深度优先搜索并且加入顶点b、e和g以及相对应的边,直到无路可走。回溯到c,但是仍然无路可走,于是回溯到b,这里加入顶点j和e以及对应的边,回溯最终又回到a。然后在d开始一个新的树并且加人顶点h、l、k和j以及对应的边。回溯到k,然后到l,然后到h并且回到d。最后,在i开始一个新的树,完成深度优先搜索。

     

    最小生成树

    定义:连通加权图里的最小生成树是具有边的权之和最小的生成树。

    普林算法

    procedure Prim(G:带n个顶点的连通加权无向图)

    T := 权最小的边 for i := 1 to n-2 e := 与T里顶点关联且若添加到T里则不形成简单回路的权最小的边 T := 添加e之后的T return T {T是G的最小生成树}

    判断是否形成简单回路可以观察边数是否等于顶点-1(不一定正确)。

     

    克鲁斯卡尔算法

    procedure Kruskal(G:带n个顶点的加权连通无向图) T := 空图 for i := 1 to n-1 e := G中权最小的任一边且当添加到T里时不形成简单回路边 T := T 添加 e return T {T是G的最小生成树}

    在普林算法里,选择与已在树中的一个顶点相关联且不形成回路的权最小的边;相对地,在克鲁斯卡尔算法里,选择不一定与已在树中的一个顶点相关联且不形成回路的权最小的边。

     

    布尔代数

    设B={0,1},则Bn={(x1,x2,,xn)|xiB,1in}是由0和1能构成的所有n元组的集合。变元x如果仅从B中取值,则称该变元为布尔变元,即它的值只可能为0或1,从Bn

    到B的函数称为n元布尔函数。

     

    布尔函数的表示

    问:给定一个布尔函数的值,怎样才能找到表示这个布尔函数的布尔表达式?

    答:任何一个布尔函数都可由变元及其补的布尔积的布尔和表示。

    有没有一个更小的运算符集合可以用来表示所有的布尔函数?

    答:所有的布尔函数都可以仅用一个运算符来表示。

     

    积之和展开式

    定义:布尔变元或其补称为字面值。布尔变元x1x2,...,xn的极小项是一个布尔积y1y2yn,其中yi=xiyi=x¯i。因此极小项是n个字面值的积,每个字面值对应于一个变元。

    举例:求一个极小项使得当x1=x3=0且x2=x4=x5=1时,它为1;否则为0。

    极小项x1x2x3x4x5有正确的值集合。

    举例:求函数F(x,y,z)=(x+y)z的积之和展开式

    F(x,y,z)=(x+y)z=xz+yz=x1z+y1z=x(y+y)z+y(x+x)z=xyz+xyz+xyz+xyz=xyz+xyz+xyz

    函数完备性

    每个布尔函数都可以表示为极小项的布尔和。每个极小项都是布尔变元或其补的布尔积。这说明每个布尔函数都可以用布尔运算·、+和⁻来表示,因为每个布尔函数都可以由这些布尔运算表示,所以我们称集合{·,+,⁻}是函数完备的。

    因为x+y=xy,所以可以消去所有的布尔和,所以{·,⁻}是函数完备的。

    因为xy=x+y,所以可以消去所有的布尔积,所以{+,⁻}是函数完备的。

    注意{+,·}不是函数完备的。

    定义运算符|或NAND如下:1|1=0且1|0=0|1=0|0=1,定义运算符↓或NOR如下:1↓1=1↓0=0↓1=0且0↓0=1。集合{|}和集合{↓}都是完备的,只需证明两个运算·和⁻可以由|或↓表示即可

    x=x|xxy=(x|y)|(x|y)
    x=xxxy=(xx)(yy)

    逻辑门电路

    构造三种组合电路:反相器、或门和与门

    image-20231028164056102

    举例:某个组织的一切事务都由一个三人委员会决定,每个委员对提出的建议可以投赞成票或反对票,一个建议如果得到了至少两张赞成票就获通过。设计一个电路,判断建议是否获得通过。

    假设输入为x、y和z,布尔函数表示为xy+xz+yz,电路如下图所示

    image-20231028164410334

    举例:假设真值表如下表所示

    xyzF(x,y,z)
    1111
    1100
    1010
    1001
    0110
    0101
    0011
    0000

    观察F(x,y,z)=1时对应的x、y和z的值,如果是0就取反,最后可以得到积之和表达式为

    F(x,y,z)=xyz+xyz+xyz+xyz

    后面还提到半加法器和全加法器的电路,不再过多介绍。

     

    电路的极小化

    积之和展开式可能存在多余的项,如下式就可以合并

    xyz+xyz=xz(y+y)=xz

    在该布尔函数的所有积之和表达式中,包含最少的布尔积而且包含最少的字面值。寻求这种积之和称为布尔函数的最小化

     

    卡洛图

    一种可视化的用于寻找最小化布尔函数的方法。

    举例:找出下式的卡洛图:(a)xy+x¯y;(b)xy¯+x¯y;(c)xy¯+x¯y+x¯y¯

    image-20231028184017501

    在化简时将相邻的进行化简,如

    image-20231028184559709

    对于三个变元,可以采用以下方法

    image-20231028184656790

    奎因-莫可拉斯基方法

    (1)将由n个变元构成的每一个极小项表示成一个长度为n的比特串,如果xi出现,则比特串的第i个位置为1;如果x¯i出现,则比特串的第1个位置为0。

    (2)根据串中1的个数将串分组

    (3)确定所有这样n-1个变元的积,它们可以通过取展开式中极小项的布尔和得到。将能够 合并的极小项表示成比特串,且这些串只在一个位置不相同。将这些n-1个变元的积用如下的串表示:如果xi出现在此积中,则此串的第i个位置为1;如果x¯i出现,则此位置为0;如果此积中没有涉及xi的字面值,则此位置为短划线。

    (4)确定所有这样n-2个变元的积,它们可以取为在前一个步骤形成的n-1个变元的积的布尔和。将能够合并的n-1个变元的积,表示成如下的串:在同一位置有一个短划线,且只在一个位置不相同。

    (5)只要可能,继续将布尔积合并成更少变元的积。

    (6)找到所有这样的布尔积:它们虽然出现,但还没有被用来形成少一个字面值的布尔积。

    (7)找到这些布尔积的最小集合,使得这些积之和表示此布尔函数。这可以用如下方法来完 成:构造一个表,列出哪些积覆盖了哪些极小项,每一个极小项必定被至少一个积覆盖。使用此表的第一步是找到所有的本原素隐含。每个本原素隐含必须被包含,因为它是覆盖某个极小项的唯一素隐含。如果找到了本原素隐含,就可以通过除去由此素隐含覆盖的极小项的行化简此表。第二步,去掉所有满足如下条件的素隐含,此素隐含覆盖一个极小项集合,此极小项集合被另一个素隐含覆盖。第三步,从表中去掉满足如下条件的极小项所在的行,覆盖此极小项的某些素隐含也覆盖另一个极小项。首先找到必须被包含的本原素隐含,然后去掉冗余的素隐含,最后找到可以被忽略的极小项,迭代此过程直到此表不再改变为止。这里使用回溯过程寻找最优解,为覆盖所有的字面值积逐步添加素隐含以寻找可能的解,在每一步都与已经找到的最优解进行比较。

    感觉不太好理解

     

    计算模型

    定义:词汇表(或字母表)V是由称为符号的元素构成的一个有限的非空集合。V上的一个词(或句子)是由V中元素组成的有限长度的字符串。空串(或零串)是不包含任何符号的字符串,记为λ,V上所有词的集合记为V。V上的一个语言是V的一个子集。

    注意,空串λ是不包含任何符号的串,它不同于空集⌀。因此{λ}是仅包含一个字符串的集合,此字符串为空串。

    V是一个由符号组成的集合,语言中的成分就是由这些符号导出的。词汇表中的某些元素不能由其他符号替换,这些元素称为终结符;词汇表中的其他元素可以用其他符号替换,它们称为非终结符

    定义:一个短语结构文法G=(V,T,S,P)由下列四部分组成:词汇表V,由V的所有终结符组成的V的子集T,V的起始符S,以及产生式集合P。集合V—T记为N,N中的元素称为非终结符。P中的每个产生式的左边必须至少包含一个非终结符。

    定义:设G=(V,T,S,P)是一个短语结构文法,w0=lz0r(即l、z0和r的连接)和w1=lz1r是V上的字符串。若z0z1是G的一个产生式,则称由w0可直接派生w1,记为w0w1,如果V上的字符串w0w1,...,wn(n≥0)满足w0w1w1w2,...,wn1wn,则称由w0可派生wn,记为w0w1。由w0得到wn的序列称为派生。

    定义:设G=(V,T,S,P)是短语结构文法,由G生成的语言(或G的语言)是起始符S能够派生的所有终结符串构成的集合,记为L(G)。即

    L(G)={wT|Sw}

    一开始介绍了一些文法,范式的内容

     

    带输出的有限状态机

    定义:有限状态机M=(S,I,O,f,g,s0)由如下部分组成:一个有限的状态集合S;一个有限的输入字母表I;一个有限的输出字母表O;一个转移函数f,f为每个状态和输入对指派一个新状态;一个输出函数g,g为每个状态和输入对指派一个输出;还有一个初始状态s0

    举例:根据状态表构造有限状态机

    image-20231028195608031

    在左表中,f代表输入0或1时的下一个状态,g代表输入0或1时的输出,刚开始状态s0,当输入0转到s1并输出1,所以s0s1上标着0,1;类似的,当输入1,状态不变并输出0,所以s0s1上标着1,0。

     

    输出与状态之间的转移相对应,这种类型的机器称为米兰机

    输出仅仅由状态确定,这种类型的有限状态机称为摩尔机

     

    不带输出的有限状态机

    串的集合

    定义:设V是一个词汇表,A、B是V的子集。A和B的连接是所有形如xy的串构成的的集合,记为AB,其中x是A中的串,y是B中的串。

    举例:设A={0,11},B={1,10,110}。求AB和BA

    集合AB包括所有A中串和B中串的连接,故AB = {01,010,0110,111,1110,11110}

    集合BA包括所有B中串和A中串的连接,故BA = {10,111,100,1011,1100,11011}

    定义:设A是V的一个子集,A的克莱因闭包是A中任意多个串的连接组成的集合,记为A,即A=k=0Ak

    有限状态自动机

    定义:有限状态自动机M=(S,I,f,s0,F)由下列五部分组成:一个有限的状态集合S;一个有限的输入字母表I;一个转移函数f,f为每个状态和输入对指派下一个状态(因此有f:S×I→S);一个初始状态或起始状态s0;一个由终结状态(或可接受状态)构成的S的子集F。

     

    非确定性的有限状态自动机

    到目前为止所讨论的有限状态自动机都是确定性的,因为对每对状态和输入值,转移函数只给出唯一的下一个状态。还有一种重要的有限状态自动机,它对每对输入值和状态,有多个可能的下一个状态,这样的机器称为非确定性的。非确定性的有限状态自动机在判断哪些语言可以由有限状态自动机识别中非常重要。

    定义:非确定性的有限状态自动机M=(S,I,f,s0,F)由下列五部分组成:一个状态的集合S;一个输入字母表I;一个转移函数f,f为每个状态和输入对指派一个状态集合(因此有f: S×I→P(S));一个初始状态s0;还有一个由终结状态构成的S的子集F。

    非确定性的有限状态自动机也可用状态表和状态图来表示。在状态表中,对每对状态和输入值,列出所有可能的F一个状态。在状态图中,从一个状态到每个可能的下一个状态,都画一条边,这条边的标号是导致这个转移的一个或多个输入。

    定理:如果语言L可以由非确定性的有限状态自动机M0所识别,则L也可以由一个确定性的有限状态自动机M来识别。

     

    语言的识别

    一个集合能够被一个有限状态自动机识别当且仅当这个集合是以任意顺序通过对空集、空串和单字符串的连接、并或克莱因闭包构造出来。以这种方法构造出来的集合称为正则集合

    定义:集合I上的正则表达式的递归定义为:

    符号⌀是一个正则表达式;

    符号λ是一个正则表达式; 若x∈I时,则符号x是一个正则表达式; 当A、B是正则表达式时,符号(AB)、(AB)和A都是正则表达式。

     

    定理(克莱因定理):一个集合是正则的,当且仅当它可由一个有限状态自动机识别。

     

    图灵机

    定义:图灵机T=(S,I,f,s0)由下列各部分组成:有限状态集S,包含空白符B的字母表I,从S×I到S×I×{R,L}的部分函数f,及初始状态s0

    图灵机主要由一个控制器和一个纸带组成,控制器在任何时候都处于有限多个不同状态中的某 个状态,纸带被分成许多方格,且两端都是无限的。当图灵机的控制器沿着纸带来回移动时,它能够在带上读和写,并根据所读的纸带符号改变状态。图灵机比有限状态自动机更强大,因为它有存储能力,而有限状态自动机却没有。

    为了用机器的观点来解释这个定义,考察控制器和纸带,如下图所示,纸带被分成小方格,且两端都是无限的,在任何时刻其上都只有有限多个非空白符。图灵机运行的每一步动作依赖于部分函数对当前状态和纸带符号的值。

    image-20231028204514563

    在每一步,控制器读当前纸带符号x,如果控制器处于状态s,且部分函数f在(s,x)处由f(s,x)=(s',x',d)定义,则控制器:

    (1)进入状态s';

    (2)在当前方格中擦掉x,并写上符号x';

    (3)如果d=R,向右移动一个方格;如果d=L,向左移动一个方格。

    我们将这一步写成五元组(s,x,s',x',d)。如果部分函数f在(s,x)处没有定义,则图灵机T 就停机。定义一个图灵机的常用方法是指明形如(s,x,s',x',d)的五元组构成的一个集合。

     

    定义:设V是字母表I的一个子集。图灵机T=(S,I,f,s0)识别V中的字符串x当且仅当若将x写在纸带上,T从初始位置开始运行,则T能在一个终结状态停机。称T能识别V的子集A,如果x能被T识别当且仅当x属于A。

     

    示例:求一个图灵机,使之能识别第二位是1的比特串构成的集合,即正则集合(01)1(01)

    我们想要如下的图灵机,它从最左边的非空白带方格开始运行,然后向右移动,同时判断第二个符号是否为1。若第二个符号是1,则机器应该进入终结状态;如果第二个不是1,则机器不能停机,或者在一个非终结状态下停机。

    为了构造这样的图灵机,应该包括五元组(s0,0,s1,0,R)和(s0,1,s1,1,R)来读第一个符号,并进入状态s1。下一步,添加五元组(s1,0,s2,0,R)和(s1,1,s3,1,R)来读第二个符号,当这个符号是0时,进入状态s2;当这个符号是1时,进入状态s3。我们不希望使第二位是0的字符串也被识别,所以s2不可能是终结状态。我们希望s3是终结状态,所以我们要加入五元组(s2,0,s2,0,R)。因为我们不想识别空串和只有一位的字符串,所以还加入五元组(s0,B,s1,0,R)和(s1,B,s2,0,R)。

    由上述7个五元组组成的图灵机T在终结状态s3终止当且仅当此比特串至少有2位,并且第二位是1。如果此比特串少于两位,或者其第二位不是1,则机器将在非终结状态s2终止。

     

    用图灵机计算函数

    可以将图灵机看作能求部分函数的值的计算机。为了理解这一点,假设给定输入字符串x时图灵机T能够停机,且停机时,字符串y在它的纸带上。因此可以定义T(x)=y。T的定义域是使T能停机的字符串构成的集合。对于输入x,若T不停机,则T(x)没有定义。将图灵机看成计算字符串的函数值的机器是有用的,但怎么用图灵机来计算定义在整数、整数对或整数三元组等上的函数呢?

    为了将图灵机看作计算k元非负整数集合到非负整数集合的函数(这样的函数称为数论函数)的计算机,需要找到在纸带上表示整数的k元组的方法。为此,我们使用整数的一元表示,即将非负整数n表示成有n+1个1的字符串。例如,0表示成字符串1、5表示成字符串111111。为了表示k元组(n1,n2,...,nk),我们先写n1+1个1,后面跟一个星号,再跟n2+1个1,再跟一个星号,等等,以nk+1个1结尾。例如,四元组 (2, 0, 1, 3) 可以表示成字符串1111111111

    举例:构造一个图灵机,它将两个非负整数相加。

    需要构造图灵机来计算函数f(n1,n2)=n1+n2。将对(n1,n2)表示成这样的字符串:先是n1+1个1后面跟一个星号,再跟n2+1个1。机器T应以这个字符串作为输入,并在纸带上产生n1+n2+1个1作为输出。实现这个任务的一个方法是,机器从输人字符串最左边的1开始运行,执行去掉这个1的步骤。若n1=0,则停机,此时,星号之前已没有1了。在剩下的1中,用最左边的1替换星号,然后停机。下列五元组能做到这一点:(s0,1,s1,B,R),(s1,,s3,B,R),(s1,1,s2,B,R),(s2,1,s2,1,R),(s2,,s3,1,R)

    不幸的是,即使是相对简单的函数,构造图灵机来计算它也是极为费力的。

     

    丘奇-图灵论题

    丘奇—图灵论题:对于任何可用有效算法来求解的问题,都存在解该问题的图灵机。

    注意不是定理

     

    计算复杂度、可计算性和可判定性

    定义:判定问题是指判断某个特定类型的命题是否为真,判定问题也被称为“是或不是”问题。

    当有一个有效的算法能够判断判定问题的某个解是否正确时,我们说这个问题是可解的或者说是可判定的

    如果不存在一个算法来解决某个问题,那么就称该问题是不可解的或者说不可判定的。为了证明某个问题是可解的,只需要构造一个算法来判定某类特定的描述是否正确。另一方面,为了证明某个问题是不可解的,需要证明不存在这样一个判定算法就可以了(事实上,我们试图找到这样的算法,但失败了,不能证明该问题是不可解的)。

    如果一个函数可以被图灵机计算,那么就称其是可计算的,否则是不可计算的

    定义:如果一个判定问题能由确定性的图灵机在多项式时间内求解,则该问题属于Р类问题,即多项式时间问题。也就说,如果一个确定性的图灵机T和一个多项式P,对于该问题的任何长度为n的字符串,T都能在P(n)步内停机,我们说该问题属于P类。如果一个判定问题能由非确定性的图灵机在多项式时间内求解,则该问题属于NP类问题,即非确定性的多项式时间问题。也就是说,对于任一判定问题,如果存在一个非确定性的图灵机T和一个多项式P,对于该问题的任何长度为n的实例,T都能在P(n)步内停机,则称该问题是NP类问题。

    P类问题称为易处理的问题,而不属于P类问题称为不易处理的问题。